二叉树的线索化

《二叉树的线索化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二叉树的线索化：以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列（先序、中序或后序序列）中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。为了保存这种在遍历过程中得到的信息，我们利用二叉链表中的空链域（由于结点没有左子树或右子树），来存放结点的前驱和后继信息。作如下规定：①若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；②若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。（1）线索链表的结点结构lchildLTagdat

2、aRTagrchild其中：data：数据域；lchild：左指针域，指向该结点的左孩子；rchild：右指针域，指向该结点的右孩子；0lchild域指示结点的左孩子LTag=1lchild域指示结点的前驱0rchild域指示结点的右孩子RTag=1rchild域指示结点的后继请将根据图1所示编写一个程序实现构建线索二叉树。thrt01bt0A00B00C01D10E01F11G11H10I01J11k1图1#include#include#include#define

3、NULL0#defineOK1#defineERROR0typedefenumPointerTag{Link,Thread};//Link==0,指向孩子；Thread==1,指向前驱后继typedefcharTElemType;typedefintStatus;//线索化二叉树的存储结构typedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;//左孩子与右孩子的指针PointerTagLTag,RTag;//左右标志域，指示是孩子还是前驱后继}B

4、iThrNode,*BiThrTree;//按照先序输入二叉树各个节点，创建原始二叉树，StatusCreateBiTree(BiThrTree&T){#表示空树charch;scanf("%c",&ch);if('#'==ch)T=NULL;else{T=(BiThrTree)malloc(sizeof(BiThrNode));if(!T)exit(ERROR);T->data=ch;T->LTag=T->RTag=Link;//建表时初始化都为CreateBiTree(T->lchild);//构造左子树CreateBi

5、Tree(T->rchild);//构造右子树Link(即0）}returnOK;}BiThrTreepre=NULL;//定义pre为函数InThreading的外部变量，使其指向最后一个节点voidInThreading(BiThrTreep);//函数声明//中序遍历二叉树，将其线索化，Thrt指向头结点StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){Thrt=(BiThrTree)malloc(sizeof(BiThrNode));//分配头结点if(!Thrt)

6、exit(ERROR);//以下三步都是在初始化头结点Thrt->LTag=Link;//假设头结点的有右孩子Thrt->RTag=Thread;//假设头结点有后继Thrt->rchild=Thrt;//暂时使头结点的右指针指向自己if(!T)Thrt->lchild=Thrt;//如果树空，就令头结点左指针指向自己else{//下面先线索头结点Thrt->lchild=T;//头结点左指针指向根pre=Thrt;//先pre指向头指针（也就是根节点的前驱)//接着线索二叉树InThreading(T);//调用函数将T线索

7、化//最后线索尾节点pre->RTag=Thread;//假设最后一点有后继pre->rchild=Thrt;//最后一个点右指针指向头结点Thrt->rchild=pre;//头结点的右指针指向最后一个点}returnOK;}//将根为p的二叉树线索化，千万记住，p是局部变量，当进入下一次递归时他会屏蔽上一个p，//但是上一个p仍然保留着，等到函数返回时他就又恢复了上一个voidInThreading(BiThrTreep){pif(p)//仅仅当p不空时才后继续下面的操作，如果{InThreading(p->lchild

8、);//左子树线索化p空，那么直接结束，不返回任何值//对于当前节点，仅仅处理他与前驱的关系if(!p->lchild){p->LTag=Thread;p->lchild=pre;}//如果当前点左边为空，指向前驱if(!pre->rchild){pre->RTag=Thr