(1) 建树算法：
1、分析：建立一个二叉链表，需要按照某种顺序依次输入二叉树中的结点，且该输入
顺序必须隐含结点间的逻辑结构的信息。这个建立的方法，按完全二叉树的层次顺序，依
次输入结点信息建立二叉链表的过程。以@表示空结点，以#表示输入结束的标志 。
2、算法思想：依次输入结点信息，若其不是虚结点，则建立一个新结点。若新结点是
第一个结点，则令其为根结点，否则将新结点作为孩子链接到它的父亲结点上。
3、实现：在函数中设置一队列，该队列是一个指针类型的数组，保存已输入的结点的
地址。使队头指针 front 指向当前与孩子建立链接的父亲结点，队尾指针 rear 指向当前输入
的结点。若 rear 为偶数，则该结点为父结点的左孩子，若 rear 为奇数，则为父结点的右孩
子。若父结点或孩子结点为虚结点，则无需链接。若父结点与其两个孩子结点链接完毕，
则使 front 指向下一个等待链接的父结点。
4、主要过程：
Bithptr *Q[maxsize]; //建队为指针类型
Bithptr *CreatTree(){
front=1;rear=0; //置空队
if(ch!='@') //不是虚结点，则建立结点
s=(Bithptr *)malloc(sizeof(Bithptr));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
s->rtag=0;
s->ltag=0;
if(s!=NULL&&Q[front]!=NULL) //孩子和双亲结点都不是虚结点
if(rear%2==0) Q[front]->lchild=s;
else Q[front]->rchild=s;
if(rear%2==1)front++; //结点*Q[front]的两个孩子处理完，front+1
(2) 线索化算法：
1、分析：线索过程必须要按照一定的顺序来进行，在本程序中因为树的遍历过程使用
的是中序遍历，所以为了方便，线索化的过程也是使用中序线索化。
2、方法：按某种遍历顺序将二叉树线索化，只需要在遍历的过程中将二叉树中每个结
点的空的左右孩子指针域分别修改为指向其前驱和后继。若其左子树为空，则将其左孩子
域线索化，使其左孩子指针 lchild 指向其后继，并且 ltag 置 1。
3、实现：要实现线索化，就要知道结点*pre 是结点*p 的前驱，而*p 是*pre 的后继。
这样，当遍历到结点*p 时，可以进行，若*p 有空指针域，则将相应的标志置 1；若*p 的左
线索标志已经建立（p->ltag==1），则可使其前驱线索化，令 p->lchild=pre；若*pre 的左
线索标志已经建立（pre->rtag==1），则可使其后继线索化，令 pre->rchild=p;
4、主要过程：
void PreThread(Bithptr *root)
{
PreThread(p->lchild); //左子树线索化
评论0
最新资源