正文描述:《数据结构课件ppt第06章03.ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库。
1、6.5线索二叉树遍历二叉树的结果是,求得结点的一个线性序列。ABCDEFGHK例如:先序序列:ABCDEFGHK中序序列:BDCAHGKFE后序序列:DCBHKGFEA何谓线索二叉树?线索线索链表线索二叉树以二叉链表为存储结构时,只能找到结点的左、右孩子信息,而不能直接得到结点在任一遍历序列中的前驱和后继信息。利用n个结点的二叉链表必定存在n+1个空链域,来存放结点的前驱和后继信息。线索:指向前驱和后继的指针。线索链表:包含“线索”的存储结构。线索二叉树:加上线索的二叉树。线索化:对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。对线索链
2、表中结点的约定:在二叉链表的结点中增加两个标志域,lchildLTagdataRTagrchildLTag=0:lchild域指示结点的左孩子LTag=1:lchild域指示结点的前驱RTag=0:rchild域指示结点的右孩子RTag=1:rchild域指示结点的后继有如下规定:若该结点的左子树不空,则Lchild域的指针指向其左子树,且左标志域的值为“指针Link”;否则,Lchild域的指针指向其“前驱”,且左标志的值为“线索Thread”。若该结点的右子树不空,则rchild域的指针指向其右子树,且右标志域的值为“指针Link”;否则,r
3、child域的指针指向其“后继”,且右标志的值为“线索Thread”。线索链表:包含五个域(lchild、LTag、data、RTag、rchild)的结点构成的二叉链表作为二叉树的存储结构。对右图进行先序线索化。对每个结点,如果该结点没有左子树,加上线索,指向其前驱。若该结点没有右子树,加上线索指向其后继。先序序列:ABCDEFGHKABCDEFGHKNILtypedefstructBiThrNod{TElemTypedata;structBiThrNode*lchild,*rchild;//左右指针PointerTagLTag,RTag;//
4、左右标志}BiThrNode,*BiThrTree;线索链表的类型描述:typedefenum{Link,Thread}PointerTag;//Link==0:指针,Thread==1:线索中序线索链表ABCDEFGHK01001001010111001111ABECFHKDGT:头指针头结点线索链表的遍历算法:for(p=firstNode(T);p;p=Succ(p))Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息,从而简化了遍历的算法。例如:对中序线索化链表的遍历算法※中序遍历的第一个结点?※在中序线索化链表
5、中结点的后继?左子树上处于“最左下”(没有左子树)的结点。若无右子树,则为后继线索所指结点;否则为对其右子树进行中序遍历时访问的第一个结点。voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(TElemTypee)){p=T->lchild;//p指向根结点while(p!=T){//空树或遍历结束时,p==Twhile(p->LTag==Link)p=p->lchild;//第一个结点if(!Visit(p->data))returnERROR;//访问左子树为空的结点while(p->RTag==T
6、hread&&p->rchild!=T){p=p->rchild;Visit(p->data);//访问后继结点}p=p->rchild;//p进至其右子树根}}//InOrderTraverse_Thr在中序遍历过程中修改结点的左、右指针域,以保存当前访问结点的“前驱”和“后继”信息。遍历过程中,附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。如何建立线索链表?voidInThreading(BiThrTreep){if(p){//对以p为根的非空二叉树进行线索化InThreading(p->lchild);//左子树
7、线索化if(!p->lchild)//建前驱线索{p->LTag=Thread;p->lchild=pre;}if(!pre->rchild)//建后继线索{pre->RTag=Thread;pre->rchild=p;}pre=p;//保持pre指向p的前驱InThreading(p->rchild);//右子树线索化}//if}//InThreadingStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//构建中序线索链表if(!(Thrt=(BiThrTree)malloc(sizeof(B
8、iThrNode))))exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->r
显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。