实验第二次.doc

实验-第二次作业
1. 实验题目
编写一个完整的程序，实现二叉树的构造及中序线索化算法，并在主函数中举出应用实例.
2.需求分析
【1】.程序的功能：按照主函数中的策略创建一棵二叉树，接着将该树实现线索化，然后按照中序遍历的遍历方式将二叉树线索化　　
【2】.输入输出要求：将二叉树的节点值按照一定的顺序进行输入，最终程序按照中序遍历的方式将二叉树的节点值进行输出，在本题中节点元素数组设为是按照5，6，4，8，2，3，7，1，9顺序进行输入的。即：已知二叉树结点值输入的数据顺序是5，6，4，8，2，3，7，1，9；按照以下策略创建二叉树并将其线索化，然后按照中序遍历的方式进行输出。
二叉树的创建策略是：
　 【1.1】将第一个要创建的元素插入成为根节点。将元素值与结点值比较，如果元素值大于结点值，将此元素送往结点的右儿子结点，如果右儿子结点不是空的，需要重复比较，否则创建结点将元素值插入。
【1.2】如果元素值小于结点值，将此元素送往结点的左儿子结点，如果左儿子结点不是空的，需要重复比较，否则创建结点将此元素值插入。
4. 算法思想：
要实现本题的要求，首先要创建一棵二叉树，该二叉树的创建策略其实就是搜索二叉树的创建原则，当数组元素大于节点元素时，则数组元素应插在当前节点的右分支上，若当前节点的右儿子为空，直接插入，否则一次依次往下比较；当数组元素小于当前节点元素时，应当将其插在当前节点的左分支上，若当前节点的左儿子为空，则直接插入，否则依次比较下去直至找到插入的位置。
　在创建好二叉树以后，便要对二叉树进行线索化，根据二叉树线索化的思想，在中序线索化的过程中，对于内节点，其前驱节点是其左子树的最右结点，其后继结点是右子树的最左节点；对于叶子节点，最左儿子的前驱为空，而最右叶子节点的后继结点为空。
线索化以后，则需对其进行中序遍历，然后对其进行输出即可。
5.数据结构
typedef struct node /*结点结构体*/
　　　{ TreeNode left;/*左指针变量*/
int ltag;/*左线索变量*/
int num;/*节点元素*/
int rtag;/*右线索变量*/
TreeNode right;/*右指针变量*/
　　　}Node
6. 模块化
　　　创建一个新的二叉树节点NewNode()
　　　创建一个大小为size空堆栈StackInit(int size)
　　　节点出栈Pop()，入栈操作Push()
　　　创建一棵二叉树CreatTree(int data[],int n,Tree T)
　　　二叉树线索化thread(Tree T)
　　　二叉树的中序遍历Inorder(Tree T)

7. 程序流程图：

8. 源程序
#include<stdio.h>
typedef struct node*TreeNode;
typedef struct node /*结点结构体*/
　{ TreeNode left;/*左指针变量*/
int ltag;/*左线索变量*/
int num;/*节点元素*/
int rtag;/*右线索变量*/
TreeNode right;/*右指针变量*/
　}Node;
typedef struct astack*Stack;
typedef struct astack /*堆栈结构体，用数组实现的*/
　{ int top;
int maxtop;
TreeNode *data;
　　}Astack;
typedef struct llist*Tree;
typedef struct llist/*二叉树结构体*/
　　{ TreeNode boot;
　　　}Llist;
/* 创建一个新的二叉树节点 */
TreeNode NewNode()
　　{ TreeNode p=(TreeNode)malloc(sizeof(Node));
p->left=p->right=NULL;
p->ltag=p->num=p->rtag=0;
return p;
　　}
/* 创建一个大小为size的堆栈 */
Stack StackInit(int size)
{ Stack S=(Stack)malloc(sizeof*S);
S->data=(TreeNode)malloc(size*sizeof(TreeNode));/*为数组data分配内存空间S->maxtop=size;
S->top=-1;
return S;
}/*入栈操作 */

void Push(TreeNode p,Stack S)
　　{ S->data[++S->top]=p;
　　　} /* 出栈操作 */
TreeNode Pop(Stack S)
　　{ return
　　　　S->data[S->top--];
　　　} /* 按照题目所给策略创建一棵二叉树 */
Tree CreatTree(int data[],int n,Tree T)
{ TreeNode p,q;
int a,i;
p=NewNode();
p->num=data[0];
T->boot=p;
for(i=1;i<n;i++)
　{
q=p=T->boot;
while(q) /*以下可以找到数组元素要插入的节点所在的位置*/ if(data[i]>q->num) /*数组元素大于节点元素*/
　　　　　　　{ a=0;
　　　　　　　　　　p=q;
q=q->right;
}
else/*数组元素不大于节点元素*/
　　　　　　　　　　　　　　{ p=q;
q=q->left;
a=1;
}
}
q=NewNode();/*创建一个新的节点*/
q->num=data[i];
if(a==0){/*当数组元素插入在右分支时*/
p->right=q;
p->rtag=1;/*右指针指向的是真正的右儿子*/
}
else{/*数组元素插入在左分支*/
p->left=q;
p->ltag=1;/*左指针指向的是真正的左儿子*/
}
}
return T;
} /* 将二叉树线索化*/
void thread(Tree T)
　{
Stack st=StackInit(15);
TreeNode p,pr;
p=T->boot;
pr=NULL;
do{
while(p)
　　　　　{ Push(p,st);
p=p->left;
}
p=Pop(st);/*此时的p为树T的最左儿子*/
/*if(pr&&!pr->right){
pr->right=p;
}*/
if(pr!=NULL){/*当p不是根节点时*/
if(pr->right==NULL) pr->right=p;
}
if(p->left==NULL){
p->left=pr;
}
pr=p;
p=p->right;
}while(p||st->top!=-1);
} /* 将二叉树按照中序遍历的方式进行输出 */
void Inorder(Tree T){/*二叉树中序遍历输出*/
TreeNode p=T->boot
while(p->left!=NULL&&p->ltag==1){p=p->left;}/*找到树的最左儿子*/
while(p!=NULL){
printf("%d",p->num);/*输出节点元素*/
if(p->right!=NULL&&p->rtag==1) {/*右儿子存在的情况下*/ p=p->right;
while(p->left!=NULL&&p->ltag==1) p=p->left;
}
else p=p->right;/*让p指向当前p的后继结点*/
}
} /* 下面是主函数 */
void main()
{
Tree T=(Tree)malloc(sizeof*T);/*定义一个二叉树变量并为之分配内存空间*/
int data[10]={5,6,4,8,2,3,7,1,9};/*数组节点元素数组*/
int n=9;
T=CreatTree(data,n,T);/*创建一棵二叉树*/
thread(T);/*将二叉树线索化*/
Inorder(T);/*将二叉树中序遍历输出*/
}
9，运行结果：

10.分析二叉树、线索二叉树的特点。
二叉树：
1.二叉树是一个有根树(rooted tree)，并且每个结点最多有2个子结点。 每个结点最多有两棵子树 且这个树若不为空节点数＝1时，即只有根节点，符合要求接点数>=2时，所有的节点只有右子树二叉树是指父节点最多有两个被称为左、右子节点的树。二叉树T或者为空或者符合下面的描述：(1) T有一个特殊的节点，称为根节点；(2) T有两个节点集合，LT和RT，分别称为T的左子树和右子树；(3) LT和RT都是二叉树。
2.二叉树是有次序的，其次序不能随意颠倒
3.二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态
4.具有3个结点的树和具有3个结点的二叉树的形态。
5.二叉树是个结点的有限集，它或者是空集， 或者由一个根结点及两棵不相交的分别称作 这个根的左子树和右子树的二叉树组成。
6.非空的二叉树, 若树叶总数(leaf/node)为 n0, 分支度为2(Full node)的总数为 n2, 则 n0 = n2 + 1。
7.满二叉树(Full Binary Tree)是每个结点都有0个或2个子结点的树。一棵有n个结点的二叉树，按满二叉树的编号方式对它进行编号，若树中所有结点和满二叉树1～n编号完全一致，则称该树为完全二叉树(Complete Binary Tree)。一棵深度为k且有2k − 1个结点的二叉树称为满二叉树(Full Binary Tree)，这种树的特点是每一层上的结点数都是最大结点数。在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树(Complete Binary Tree)。具有n个结点的完全二叉树的深度为log2n + 1。深度为k的完全二叉树，第k层至少有2k − 1个结点，至多有2k − 1个结点。
8.存储方式：
【1】顺序储存：顺序储存使用一个数组，这个数组中按照被储存的二叉树的满二叉树从上到下从左到右对节点进行储存，如果被储存二叉树为非满二叉树，那么相应的位置用特殊符号标示。
【2】链表储存：链表方式储存可以分为二叉链表和三叉链表两种方式。二叉链表指的是链表节点当中除了存放节点的数据项外在存放两个指针用来分别指向左孩子和右孩子。三叉链表指的是在二叉链表的基础上增加一个指针用来指向其双亲
线索二叉树的特点：
线索二叉树是一种物理结构，其使用的对象：树节点中没有使用的n-1个空指针（n个树节点，空指针永远都是n+1个）。
数据结构：在树节点的结构是（data，*lchild，*rchild）线索树的节点是（data，*lchild，*rchild，ltag，rtag），tag为1表示线索数的节点，为0标识树节点。
运行的原则：某种深度遍历顺序——先序，中序，后序：过程：按照中序（当然也可以是其他的遍历）的前驱后继关系，若p的左子树为空，则左子树指向p的中序前驱，若p的右子树为空，则p的右子树节点指向p的后继，若是子树都有，就不用捣腾了。第一个节点的左子树为空（此节点一定是叶节点，而且没前驱，所以是空），最后一个节点的右子树也是空。
目的：方便找到树在某种遍历的条件下前驱和后继。不是用来遍历的哈。
二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。
对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的指针fwd和bkd，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。现将二叉树的结点结构重新定义如下：
lchild ltag data rtag rchild
其中：ltag=0 时 lchild指向左子女；
ltag=1 时 lchild指向前驱；
rtag=0 时 rchild指向左子女；
rtag=1 时 rchild指向后继；以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，指向前驱和后继的指针叫线索，加上线索的二叉树叫线索二叉树，对二叉树进行某种形式遍历使其变为线索二叉树的过程叫线索化。
线索化的注意点：只用中序线索树可以很完美的达到这个效果，前序线索树在计算前驱的时候会牵扯到自己的父节点，就要使用栈来找，这样和遍历查找没区别，同理，后序线索树找后继会比较麻烦。
中序实现的一个要点：找前驱：向左找第一个rtag为1的就是它的前驱了。因为在中序中，所有的内节点（非叶节点）的前驱和后继必然是一个叶节点。
在线索化之前，需要分析考虑的：一是何种“序”的线索化，是先序、中序还是后序；二是要“前驱”线索化、“后继”线索化还是“全”线索化（前驱后继都要）；三是只有空指针处才能加线索。