数据结构二叉树的线索本.ppt
第六章 线索二叉树,本讲内容,1.线索的定义,2.线索二叉树,3.线索链表,4.线索化,5.线索二叉树的应用,为什么引入线索的概念,遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列。,先序序列,中序序列,后序序列,遍历二叉树实质上对一个非线性结构进行线性化操作，使每一个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。,当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一遍历序列中的直接前驱和直接后继信息，这种信息只有在遍历的动态过程中才能得到。,线索的定义,为了解决上述问题，二叉树采用二叉树链表作为存储结构时，为了不降低存储密度，可以利用二叉链表中存储的空指针域来存放结点的直接前驱或直接后继信息，即指向直接前驱或直接后继。,结点没有左孩子,lchild指向直接前驱,前驱线索,结点没有右孩子,rchild指向直接后继,后继线索,线索二叉树,加上线索的二叉树称之为线索二叉树。为了区分方便，在线索二叉树中，指针用实线表示，线索用虚线表示。,中序线索二叉树,线索链表,二叉树的另一种链式存储结构。,约定结点,在二叉链表的结点中增加两个标志域，并作如下规定：,若该结点的左子树不空，则lchild域的指针指向其左子树，且左标志域的值为“指针ltag=0”；否则，lchild域的指针指向其“前驱”，且左标志的值为“线索ltag=1”。,若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针rtag=0”；否则，rchild域的指针指向其“后继”,且右标志的值为“线索rtag=1”。,线索链表类型C描述,typedef struct BiThrNode ElemType data;struct BiThrNode*lchild,*rchild;/指针或线索 int ltag,rtag;/标志域，等于0为指针，等于1为线索 BiThrNode,*BiThrTree;,为方便起见，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向遍历时访问的最后一个结点；反之，令二叉树遍历序列的第一个结点的lchild域的指针和最后一个结点的rchild域的指针均指向头结点。,线索化,对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。,线索化的实质就是将二叉链表中的空指针改为指向直接前驱或直接后继的线索。,线索化的过程即为在遍历的过程中修改空指针的过程，即在“访问根结点”处进行加线索的改造，就可实现前序、中序和后序的线索化。,线索化分类,前序线索化,中序线索化,后序线索化,中序线索化举例,A,B,D,E,G,C,F,H,中序遍历序列：DBEGAFHC,NULL,NULL,方法：在遍历过程中修改空指针或先写出遍历序列，标出空指针，对照再画出线索。,线索二叉树的应用,例1：中序线索二叉树的遍历算法,例2:编写算法实现对二叉树的前序线索化,例3:编写算法实现对二叉树的中序线索化,例4:求中序线索树中给定值为x的结点之后继结点,例5:求后序线索树中给定结点p的直接前驱q,例1：中序线索二叉树的遍历算法,如何寻找中序遍历中的第一个结点？,如何在中序线索二叉树中寻找结点的后继？,若无右子树，则为后继线索所指结点；,否则为对其右子树进行中序遍历时访问的第一个结点。,左子树上处于“最左下”（没有左子树）的结点。,不借助辅助堆栈实现中序遍历，而是利用线索树来完成。,中序线索树的遍历算法实现,void InOrder(BiThrTree T,void(*Visit)(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有右子树，进入其右子树根/InOrder,例2：二叉树的前序线索化,算法思想,对二叉树进行前序遍历，在“访问结点”时根据有无左右孩子判断决定进行加线索的改造。没有左孩子添加前驱线索，没有右孩子添加后继线索。,需要设一个指针pre始终指向当前访问结点的前驱,二叉树的前序线索化算法实现,BiThrTree pre=NULL;/设置前驱为全局void PreOrderThread(BiThrTree T)if(T)if(!T-lchild)/左孩子为空，添加前驱线索T-ltag=1;T-lchild=pre;/修改前驱线索为pre if(pre/右子树前序线索化,例3:二叉树的中序线索化算法实现,BiThrTree pre=NULL;/设置前驱为全局void InOrderThread(BiThrTree T)if(T)InOrderThread(T-lchild);/左子树中序线索化 if(!T-lchild)/左孩子为空，添加前驱线索T-ltag=1;T-lchild=pre;/修改前驱线索为pre if(pre/右子树中序线索化,例4：求出给定值x的后继结点,算法思想,假设在中序线索二叉树进行操作，采用带头结点的线索链表作为存储结构。首先，在中序线索二叉树中查找给定值为x的结点，由p指向；然后，根据指针p在中序线索二叉树中所指结点的后继结点的特征进行判断。,特征：若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/转向右子树寻找,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)q=q-lchild;/右子树中最左下的结点为所求后继return(q);,例5：求后序线索树中给定结点的直接前驱,算法思想,二叉树的后序遍历是“左-右-根”，因此，在后序线索二叉树中，若结点有右子女，则右子女是其后序前驱；否则，左子女（或左线索）指向其后序前驱。,BiThrTree PostFront(BiThrTree T,BiThrTree p)if(p-rtag=0)return(p-rchild);/若p有右子女，则右子女为其前驱elsereturn(p-lchild);/若p无右子女，则左子女或左线索为其直接前驱,
