数据结构二叉树的线索本.ppt

《数据结构二叉树的线索本.ppt》由会员分享，可在线阅读，更多相关《数据结构二叉树的线索本.ppt（20页珍藏版）》请在优知文库上搜索。

1、第六章 线索二叉树本讲内容1.线索的定义线索的定义2.线索二叉树线索二叉树3.线索链表线索链表4.线索化线索化5.线索二叉树的应用线索二叉树的应用为什么引入线索的概念遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列。 先序序列先序序列中序序列中序序列后序序列后序序列遍历二叉树实质上对一个非线性结构非线性结构进行线性化操作线性化操作，使每一个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继仅有一个直接前驱和直接后继。 当以当以二叉链表二叉链表作为存储结构时，只能找到结点的作为存储结构时，只能找到结点的左、右孩子左、右孩子信信息，而息，而不能直接不能直接得到结点在任

2、一遍历序列中的得到结点在任一遍历序列中的直接前驱和直接直接前驱和直接后继后继信息，这种信息信息，这种信息只有在遍历的动态过程中才能得到只有在遍历的动态过程中才能得到。 线索的定义为了解决上述问题，二叉树采用二叉树链表作为存储结构时，为了不降低存储密度，可以利用二叉链表中存储的空指针域来存放结点的直接前驱或直接直接前驱或直接后继后继信息，即指向直接前驱或直接后继指向直接前驱或直接后继。 结点没有左孩子结点没有左孩子lchild指向直接前驱指向直接前驱前驱线索前驱线索结点没有右孩子结点没有右孩子rchild指向直接后继指向直接后继后继线索后继线索线索二叉树加上线索的二叉树称之为线索二叉树。为了区分

3、方便，在线索二叉树中，指针用实线表示，线索用虚线表示。 ABCDEGFHNULLNULL中序线索二叉树中序线索二叉树线索链表二叉树的另一种链式存储结构链式存储结构。 约定结点约定结点在二叉链表的结点中增加两个标志域增加两个标志域，并作如下规定：若该结点的左子树不空，则lchild域的指针指向其左子树，且左标志域的值为“指针ltag=0”； 否则，lchild域的指针指向其“前驱”，且左标志的值为“线索ltag=1”。若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为 “指针rtag=0”；否则，rchild域的指针指向其“后继”,且右标志的值为“线索rtag=1”。 线

4、索链表类型C描述typedef struct BiThrNode ElemType data; struct BiThrNode *lchild, *rchild; /指针或线索 int ltag, rtag; /标志域，等于0为指针，等于1为线索 BiThrNode, *BiThrTree;lchild ltagdatartag rchild0/10/1为方便起见，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点添加一个头结点，并令其lchildlchild域的指针指向二叉树的根结点根结点，其rchildrchild域的指针指向遍历遍历时访问的最后一个结点最后一个结点；反之，令二叉

5、树遍历序列的第一个结点第一个结点的lchildlchild域的指针和最后一个结点最后一个结点的rchildrchild域的指针均指向头结点指向头结点。 010 A 0thrt0 C 11 F 01 H 100 B1 E 0G1D 111线索化对二叉树以某种次序遍历使其变为线索二叉树变为线索二叉树的过程过程叫做线索化线索化。 线索化的实质实质就是将二叉链表中的空指针空指针改为改为指向指向直接前驱直接前驱或直接后继直接后继的线索线索。 线索化的过程即为在遍历的过程中修改空指针的过在遍历的过程中修改空指针的过程程，即在“访问根结点”处进行加线索加线索的改造，就可实现前序、中序和后序的线索化。 线索化

6、分类线索化分类前序线索化前序线索化 中序线索化中序线索化 后序线索化后序线索化 中序线索化举例ABDEGCFH中序遍历序列：中序遍历序列：DBEGAFHCNULLNULL方法：方法：在遍历过程中修改空指针在遍历过程中修改空指针或先写出遍历序列，标出空指针，或先写出遍历序列，标出空指针，对照再画出线索。对照再画出线索。线索二叉树的应用例例1：中序线索二叉树的遍历算法：中序线索二叉树的遍历算法例例2:编写算法实现对二叉树的前序线索化编写算法实现对二叉树的前序线索化例例3:编写算法实现对二叉树的中序线索化编写算法实现对二叉树的中序线索化例例4:求中序线索树中给定值为求中序线索树中给定值为x的结点之后

7、继结点的结点之后继结点例例5:求后序线索树中给定结点求后序线索树中给定结点p的直接前驱的直接前驱q例1：中序线索二叉树的遍历算法 如何寻找中序遍历中的第一个结点？如何寻找中序遍历中的第一个结点？ 如何在中序线索二叉树中寻找结点的后继？如何在中序线索二叉树中寻找结点的后继？若无右子树，则为后继线索所指结点后继线索所指结点；否则为对其右子树其右子树进行中序遍历中序遍历时访问的第一个第一个结点结点。左子树上处于“最左下最左下”（没有左子树）的结点。不借助辅助堆栈实现中序遍历，而是利用线索树来完成。中序线索树的遍历算法实现void InOrder(BiThrTree T ,void (*Visit)(

8、TElemType e) p = T-lchild; / p指向根结点 while (p != T) / 空树或遍历结束时，p=T while ( p-ltag=0 ) p = p-lchild; / 第一个结点为最左下没有左子树的结点 visit(p-data) ;while ( p-rtag=1 & p-rchild!=T ) /没有右子树时，即为后继线索时找其后继结点 p = p-rchild; visit (p-data); / 访问后继结点 p = p-rchild; /p有右子树，进入其右子树根 / InOrder例2：二叉树的前序线索化算法思想算法思想对二叉树进行前序遍历，在“访

9、问结点”时根据有无左右孩子判断决定进行加线索的改造。没有左孩子添加前驱线索，没有右孩子添加后继线索。需要设一个指针需要设一个指针pre始终指向始终指向当前访问结点当前访问结点的的前驱前驱二叉树的前序线索化算法实现BiThrTree pre = NULL ; /设置前驱为全局void PreOrderThread(BiThrTree T)if(T) if( !T-lchild ) /左孩子为空，添加前驱线索T-ltag = 1 ;T-lchild = pre ; /修改前驱线索为pre if( pre & pre-rtag=1 ) /前驱结点没有右孩子 pre-rchild = T ; /前驱结

10、点的后继为当前结点 if( !T-rchild ) T-rtag = 1; /置右标记，为后继线索做准备 pre = T ; if( T-ltag=0 ) PreOrderThread( T-lchild ); /左子树前序线索化 PreOrderThread( T-rchild ); /右子树前序线索化例3:二叉树的中序线索化算法实现BiThrTree pre = NULL ; /设置前驱为全局void InOrderThread(BiThrTree T)if(T) InOrderThread( T-lchild ); /左子树中序线索化 if( !T-lchild ) /左孩子为空，添加前

11、驱线索T-ltag = 1 ;T-lchild = pre ; /修改前驱线索为pre if( pre & pre-rtag=1 ) /前驱结点没有右孩子 pre-rchild = T ; /前驱结点的后继为当前结点 if( !T-rchild ) T-rtag = 1; /置右标记，为后继线索做准备 pre = T ; InOrderThread( T-rchild ); /右子树中序线索化例4：求出给定值x的后继结点算法思想算法思想假设在中序线索二叉树进行操作，采用带头结点带头结点的线索链表作为存储结构。首先，在中序线索二叉树中查找给定值为查找给定值为x的结点，由p指向；然后，根据指针p在

12、中序线索二叉树中所指结点的后继结点的特征所指结点的后继结点的特征进行判断。特征：特征：若若p的的右标志为右标志为1，p的的rchild指向其指向其后继后继结点；结点；否则，结点否则，结点p的的右子树中最左边右子树中最左边的结点是的结点是p的中序的中序后后继继结点。结点。例4:求给定值x的后继结点BiThrTree InOrder(BiThrTree T, ElemType x)p = T-lchild ; /p指向中序线索二叉树的根结点while(p!=T)while( p-ltag=0 & p-data!=x ) p = p-lchild ; /在左子树中往左下方向查找xif(p-data=

13、x)return (p); /找到返回pwhile( p-rtag=1 & p-rchild!=T )p = p-rchild ; /后继结点if(p-data=x)return (p);p = p-rchild ; /转向右子树寻找BiThrTree AfterXNode(BiThrTree T)BiThrTree p =InOrder(T,x); /在T树上查找给定值x的结点，由p指向if( p-rtag=1 )return (p-rchild) ; /右标志为1，p的rchild指向其后继结点elseq = p-rchild ; /右标志为0，进入右子树while( q-ltag=0 )

14、 q = q -lchild ; /右子树中最左下的结点为所求后继return (q);例5：求后序线索树中给定结点的直接前驱算法思想算法思想二叉树的后序遍历是“左左-右右-根根”，因此，在后序线索二叉树中，若结点有右子女有右子女，则右子女是其后序右子女是其后序前驱前驱；否则，左子女（或左线索）指向其后序前驱左子女（或左线索）指向其后序前驱。BiThrTree PostFront(BiThrTree T,BiThrTree p)if( p-rtag=0 )return (p-rchild) ; /若p有右子女，则右子女为其前驱elsereturn (p-lchild); /若p无右子女，则左子女或左线索为其直接前驱