数据结构及其算法_6树2复习

1、2014/10/31第6章树和二叉树Treeand BinaryTree主讲：(3)兵1二叉树 线索二叉树的概念线索二叉树类型定义：typedef struct BiTreNode ElemTypedata;struct BiThrNode*lchild, *rchild; struct BiThrNode*prior, *next;BiThrNode, *BiThrTree;二叉树 线索二叉树 线索二叉树的概念A先序序列：ABDGCEFBC中序序列：BGDAECF后序序列：GDBAEFADEFG如何在遍历过程中保留下结点的前驱和后继的信息呢？最现成的办法是给每个结点增加两个指针，分别指向前驱

2、和后继。但这样做无疑增大了空间的开销。指向前驱的线索指向后继的线索priorlchilddatarchildnext二叉树 线索二叉树 线索二叉树的概念一、 线索二叉树的概念A先序序列：ABDGCEFBC中序序列：BGDAECFDEF后序序列：GDBEFCAG二叉树的遍历序列是线性序列。在二叉树上找某个结点在某种遍历序列中的直接前驱或直接后继，只能在对二叉树遍历时动态求得。二叉树 线索二叉树6.3.6 线索二叉树一、线索二叉树的概念二、线索化三、遍历线索二叉树二叉树 遍历二叉树和线索二叉树6.3 遍历二叉树和线索二叉树先序、中序和后序遍历算术表达式的二叉树表示二叉树的运算举例按层次遍历二叉树创

3、建二叉链表线索二叉树2014/10/31二叉树 线索二叉树的概念A结点的中序线索二叉树不NULLBCNULLEFDG中序序列的终点A BC中序序列的起始点D E F G 二叉树 线索二叉树的概念A结点的中序线索二叉树左、右线索形成双向循环链头结点NULLBCNULLEFDG中序序列的起始点中序序列的终点2二叉树 线索二叉树 线索化二、线索化 所谓线索化，就是在已知二叉链的前提下，填写每个结点左线索prior域和右线索next域 若要建立中序线索，则在中序遍历过程中完成线索化操作； 若要建立先序线索，则在先序遍历过程中完成线索化操作； 若要建立后序线索，则在后序遍历过程中完成线索化操作；二叉树

4、线索二叉树6.3.6 线索二叉树一、线索二叉树的概念二、线索化三、遍历线索二叉树GFEDCBA二叉树 线索二叉树的概念先序线索二叉树:NULLAABCBCNULLDEFDEFGG先序序列： ABDGCEF先序线索二叉树priorlchilddatarchildnext二叉树 线索二叉树的概念中序线索二叉树:AANULLBCBCNULLDEFDEF GG中序序列 BGDAECF中序线索二叉树2014/10/31二叉树 线索二叉树 线索化二叉树 线索二叉树 线索化void InOrderThreading(BiThrTree &H, BiThrTree T) 线索化的算法原理：以中序线索化为例。对

5、二叉树做中序遍历，在对每/ 中序线索化二叉树T，形成/用H返回头结点的指针结点的双向循环线索链表个结点的时，完成下列线索的：H=new BiThrTree; /申请头结点H-lchild=T; H-rchild=NULL;if(!T) H-prior=H-next=H; /空二叉树elsepre=H;hreading(T, pre);p -next=H; H-prior=pre;/此时，pre指向中序序列的最后一个结点/else /InOrderThreading（设：p指针指向当前正在pre-next=p;p-prior=pre; pre=p;的结点；pre指向p的中序前驱）prexpx是y

6、的中序前驱二叉树 线索二叉树 线索化voidhreading(BiThrTree p, BiThrTree &pre) /对二叉树p做中序遍历，填写前驱线索和后继线索if (!p) return ; /空二叉树hreading(p-lchild, pre); pre-next=p;p-prior=pre;pre=p;hreading(p-rchild, pre);/hreading/线索化树/线索化右二叉树 线索二叉树 遍历线索二叉树二叉树 线索二叉树 遍历线索二叉树void Traverse（BiThrTree H)三、遍历线索二叉树/H是结点线索二叉树的头指针索二叉树中，由于可以直接找到每

7、个结点的后继或前驱，所以遍历可以用非递归的方法实现，而且不必借助栈。/若H是先序线索，则做先序遍历；/若H是中序线索，则做中序遍历；/若H是后序线索，则做后序遍历；p=H-next; /p指向遍历序列的第一个结点while（p!=H)visite(p-data);p=p-next;/while/Traverse这是一个通用的遍历函数。递归，也不需要用栈。索的指引下，遍历过程既不需要3二叉树 线索二叉树6.3.6 线索二叉树一、线索二叉树的概念二、线索化三、遍历线索二叉树y2014/10/31二叉树 线索二叉树 遍历线索二叉树二叉树 线索二叉树的概念void Converse_Traverse（

8、BiThrTree H)另一种线索二叉树的处理技术是：利用二叉链表中的空指针做线索：/H是结点线索二叉树的头指针/驱线索指引下对H做逆向遍历BiThrTree p=H-prior; /p指向遍历序列的终端结点while（p!=H)visite(p-data);p=p-prior; /指针向前驱方向移动/while/Converse_Traverse二叉链表中含有n+1个空指针，利用这些空指针来结点的前驱和后继的信息。约定:用空的左指针指向前驱结点，称为左线索；用空的右指针指向后继结点，称为右线索。二叉树 线索二叉树的概念A二叉树 线索二叉树的概念ABCBCEFEFDDGG红色的虚线都是线索不结

9、点的中序线索二叉树结点的中序线索二叉树41G11F11E10D10 C 01B00A0011G11F11E10D10C01B00A0二叉树 线索二叉树的概念利用空指针做线索的中序线索二叉树:AANULLBCBCNULLDEFDEFGG中序序列 BGDAECF中序线索二叉树二叉树 线索二叉树的概念A为了区别指针与线索，增加BC两个标志域LTag和RTag：DEFGlchild是左指针，指向左孩子LTaglchild是左线索，指向前驱结点0 rchild是右指针，指向右孩子RTag1 rchild是右线索，指向后继结点lchildLTagdataRTagrchild2014/10/31二叉树 线索

10、二叉树 遍历线索二叉树如何在中序线索二叉树上找中序后继如果结点p没有右孩子，则可通过右线索直接得到后继；如果结点p有右孩子，p的后继是中序遍历p的右时的第一个结点，即p的右上的“最左下点”, 即从右的根开始，沿左链一直摸到没有左孩子的结点为止。二叉树 线索二叉树 遍历线索二叉树二叉树 线索二叉树 遍历线索二叉树pBiThrTree InOrderNext(BiThrTree p) /求p的中序后继if (p-RTag=1) return p-rchild;如何在中序线索二叉树上找中序前驱如果结点p没有左孩子，则可通过左线索直接得到前驱；如果结点p有左孩子，p的前驱是中序遍历p的左s=p-rch

11、ild;/s指向右根while(s-LTag=0) s=s-lchild;return s;时的最后一个结点，即p的树上的“最s右下点”, 即从树的根开始，沿右链一直摸到没有右孩子的结点为止。求p的右的最左下点:s=p-rchild;while(s-LTag=0) s=s-lchild5二叉树 线索二叉树的概念请注意：在这种利用空指针做为线索的线索二叉树中，判断p结点是否为叶子的条件应为：p-LTag=1 & p-RTag=1二叉树 线索二叉树的概念利用空指针做线索的后序线索二叉树:AABCBCDEFNULLDEF GG后序序列： GDBEFCA后序线索二叉树二叉树 线索二叉树的概念利用空指针

12、做线索的先序线索二叉树:AABCBCNULLDEFDEFGG先序序列： ABDGCEF先序线索二叉树2014/10/31二叉树 线索二叉树 遍历线索二叉树psp的树的最右下点:s=p-lchild;while(s-RTag=0) s=s-rchild二叉树 线索二叉树 遍历线索二叉树二叉树 线索二叉树 遍历线索二叉树如何在后序线索二叉树上找后序前驱？如果结点p没有左孩子，则可通过左线索直接得到前驱；如果结点p有左孩子，根据后序遍历的规则，如果p有右孩子，则p的前驱是p的右孩子；否则是p的左孩子。如何在后序线索二叉树上找后序后继？p若是根，则p无后继；若p是双亲的右孩子或p是左孩子且无右兄弟，则

13、p的后继是双亲。BiThrTreetOrdrior(BiThrTree p) p是左孩子且有右兄弟，则p的后继应是后序遍历p的双亲/求p的后序前驱if(p-LTag=1) return p-lchild; if(p-RTag=0) return p-rchild;else return p-lchild;的右时的第一个结点双亲的右上 “最左下的叶子”。可见，在后序线索二叉树上找后序前驱比较容易可见，这种后序线索对找后序后继帮助不大，需要知道双亲二叉树 线索二叉树 遍历线索二叉树F二叉树 线索二叉树 遍历线索二叉树BiThrTreetOrderNext(BiThrTree p) /求p的后序后继

14、, 设F是p的双亲指针。if（p-RTag=1) return p-rchild; /有右线索if(!F) return NULL; /p是根，无双亲if(p=F-rchild|p=F-lchild&F-RTag=1) return F; /p是F的右孩子或p是F左孩子且F没有右孩子s=F-rchild;while(s-LTag=0|s-RTag=0)s = s-lchild ? s-lchild : s-rchild;psF右/令s找F右return s;上的最左下的叶子上最左下叶子可见，在后序线索二叉树上找后序后继比较道双亲。，往往需要知6BiThrTree InOrdrior(BiThr

15、Tree p) /求p的中序前驱if (p-LTag=1) return p-lchild;s=p-lchild;/s指向树根while(s-RTag=0) s=s-rchild; return s;二叉树 线索二叉树 遍历线索二叉树看到了吧，利用中序线索找前驱和后继虽然有时候不够直接，但还算容易。2014/10/31二叉树 线索二叉树 遍历线索二叉树对先序线索二叉树也有类似的情况，结论是：序线索二叉树中，通过线索找每个结点的先序后继容易；找先序前驱时，若存有左线索则直接找；若没有左线索，就需要知道双亲的指针啦。第六章 树和二叉树目录6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和

16、线索二叉树6.4 树和森林具体情况可参照后序线索二叉树自己分析。6.5树及其应用6.6 树的计数树的结构 双亲表示法6.4 树和森林一、双亲表示法dataparent6.4.1 树的结构0root=11234567891011双亲表示法孩子表示法带双亲的孩子链表孩子兄弟表示法树、森林与二叉树的关系树转换成二叉树森林转换成二叉树二叉树转换成森林树和森林的遍历ABCDEFGHIJK树的结构 孩子表示法树的结构 孩子表示法 孩子链表二、孩子表示法多叉链表二、孩子表示法孩子链表dataAchildB CDT01234567891011root=1EFGHIAAJKBCDDEFGHIJK设树的度为K，空

17、指针数nK(n1)n(K1)17109475836211ABCHKFGDIJEchildnextKJIHGFECBA0B1C1D1E2F2G4H4I4J5K82014/10/31树的结构 孩子表示法 孩子链表typedef struct CTNode child; struct CTNode *next; CTNode，*Childptr;树的结构 孩子表示法 双亲的带孩子链表三、带双亲的孩子链表data parentchild/孩子结点01234567891011ABCDtypedef struct /表头结点emType ChildPtr CTBox;data;EFGHIchild;JK/

18、树typedef struct CTBox nodesmaxsize; /结点数和根下标n, root CTree;树的结构 孩子表示法 孩子链表树的结构 孩子表示法 孩子链表struct CTNode /孩子结点child;typedefdatachildT可用孩子链表来表示森林0123456789101112struct CTNode *next; CTNode，*Childptr;ForestAE01234typedef struct /表头结点emType data;BCChildPtr CTBox;child;DHtypedef struct CTBox nodesmaxsize;f

19、orest10,n, ntree; /森林、结点数和树数 CTree;FIJKGL树的结构 孩子兄弟链表树的结构 孩子兄弟链表树用二叉链表表示时，树就具有了二叉树的形态：四、孩子兄弟链表AAchild data nextsiblingBCD长子数据 右邻兄弟BCDEFGHIEFGHIJKA JKB CD E F GH I J K 8KJIHGFEDCBA411297datachild156812310childnextAJCDEFGHIBKL10947datachild5836211A0B1C1H8K4F2G8D1I8J11E2childnext2014/10/31树、森林与二叉树的关系 树转

20、换成二叉树6.4 树和森林6.4.2 树、森林与二叉树的关系1. 树转换成二叉树6.4.1 树的结构双亲表示法孩子表示法带双亲的孩子链表孩子兄弟表示法树、森林与二叉树的关系树转换成二叉树森林转换成二叉树二叉树转换成森林树和森林的遍历树用孩子兄弟链表表示时，就已转化成二叉树了。一棵树可以唯一地转换成一棵右二叉树。为空的9树、森林与二叉树的关系 森林转换成二叉树AEFHBCGI JK DLEFHCGI JK DL第1步： 将森林中的每棵树转换成二叉树树、森林与二叉树的关系 森林转换成二叉树森林转换成二叉树直观的转换方法：把森林中的每一棵树转换成二叉树将所有二叉树的树根用线相连以第一棵二叉树的树根为

21、圆心，顺时针转45度树、森林与二叉树的关系 树转换成二叉树AABCDBCDEFGHIEFGHIJKJK把树中所有的兄弟之间用树枝相连；每个结点仅保留与长子的连线，删除结点与其余孩子的连线；以树根为圆心，顺时针转45度。树、森林与二叉树的关系 树转换成二叉树下面介绍直观的转换方法：把树中所有的兄弟之间用树枝相连；每个结点仅保留与长子的连线，删除结点与其余孩子的连线：以树根为圆心，顺时针转45度2014/10/31树、森林与二叉树的关系 森林转换成二叉树森林转换成二叉树的形式定义：P134森林F T1, T2, ., Tm 二叉树B(root, LB,RB) :(1)若F为空，则B为空二叉树.(2

22、)若F非空，则B的根root是T1的根；B的树由T1的森林转换而成；B的右成.由F中除第一棵树以外的剩余树转换而树、森林与二叉树的关系 二叉树换转成森林二叉树转换成森林的形式定义：P134二叉树B(root,LB, RB) 森林F T1, T2, ., Tm (1) 若B为空，则F为空(2) 若B非空，则F中T1的根是B的根；T1的根的森林由B的树LB转换而成；F中除第一棵树以外的剩余树由B的右而成。RB转换10ABEDCFGHIJLKAEFHBCGI JK DL树、森林与二叉树的关系 二叉树转换成森林二叉树转换成森林直观的转换方法：在二叉树中，设B是A的左孩子，则把B的右孩子，右孩子的右孩子

23、，.，都与A用线相连；去掉所有双亲到右孩子的连线树、森林与二叉树的关系 森林转换成二叉树AEFHBCGI JK DALBEDCFGHIJ第3步： 顺时针转45度LK树、森林与二叉树的关系 森林转换成二叉树AEFHBCGI JK DLEFHCGI JK DL第2步： 将每棵二叉树的根用树枝连起来2014/10/31树和森林 树和森林的遍历6.4 树和森林6.4.3 树和森林的遍历1. 先序遍历树6.4.1 树的结构双亲表示法孩子表示法带双亲的孩子链表孩子兄弟表示法树、森林与二叉树的关系树转换成二叉树森林转换成二叉树二叉树转换成森林树和森林的遍历若树不空，则(1)根；(2)从左至右先序遍历根的各个

24、。2. 后序遍历树若树不空，则(1)从左至右后序遍历根的各个。(2)根。树和森林 树和森林的遍历树和森林 树和森林的遍历举例：先序遍历树void preorder(CTBox tree ,datachildroot) 01234567891011root=1A/先序遍历树，树用孩子链表表示ChildPtr p;if(root=0) return; /空树/辅助指针变量BCDf(“%c”,treeroot.data); /根prEFGHIchild; /p为根的孩子链头指针p=treeroot.JKwhile(p)/沿着孩子链从左至右先序遍历根的各个 preorder(tree, p-child

25、);p=p-next;A B E J F C D G H KI11111098765432ABCDEFGHIJKchildnext树和森林 树和森林的遍历先序遍历树，等价于先序遍历由这棵树转换而成的二叉树；后序遍历树，等价于中序遍历由这棵树转换而成的二叉树；树和森林 树和森林的遍历AABECBCDJFEFG HIGJKHK先序序列：ABEJFCDGHKI中序序列：JEFBCGKHIDA后序序列：JFEKIHGDCBA先根序列：ABEJFCDGHKI后根序列：JEFBCGKHIDA2014/10/31树和森林 树和森林的遍历树和森林 树和森林的遍历3. 先序遍历森林：若森林不空，则第一棵树的根结

26、点； 先序遍历第一棵树根结点的举例：后序遍历树voidtorder(CTBox tree ,root) /后序遍历树，树用孩子链表表示if(root=)return;森林；先序遍历森林中去掉第一棵树后剩下的树的森林p=treeroot.child;while(p)/沿着孩子链从左至右后序遍历根的各个 torder(tree, p-child);p=p-next;4. 中序遍历森林：若森林不空，则中序遍历第一棵树根结点的第一棵树的根结点；森林；/访根prf(“%c”,treeroot.data);中序遍历森林中去掉第一棵树后剩下的树的森林举例：计算树的高度，树用孩子兄弟链表表示TreeHeight (CSTree T) /树高1max1高，hmax=0, h;if(!T) return 0;2高，.，m高）/空树p=T-while(p)child;h=TreeHeight(p);if(hhmax) hmax=h;/求以p为根的高度p=p-nextsibling; /p指向下一棵的根return(1+hmax);树和森林 举例二叉树 遍历二叉树 二叉树运算举例举例：打印二叉树中树根到每个树叶的路径void PrRoute(BiTree T)/利用栈S保存树根到当前结点的路径举例：计算森林的深度，森林用二叉链表表示Forest