《数据结构 6树和二叉树C》由会员分享，可在线阅读，更多相关《数据结构 6树和二叉树C（26页珍藏版）》请在金锄头文库上搜索。
1、第6章 树和二叉树 （ Tree p-lchildpre;/p的前驱结点指针pre存入左空域若pre-rchildNULL, 则pre-Rtag1;pre-rchild=p;/p存入其前驱结点pre的右空域4线索二叉树的生成算法（算法6.6, 见教材P134 ）00A00B11E00D11I11H0-Thrt1preInThreading(A)-InThreading(B)-InThreading(D)-InThreading(H)-InThreading()-17,18,19-InThreading()-InThreading(I)ppppTpreppre53. 线索二叉树的遍历理论上，只要
2、找到序列中的第一个结点，然后依次访 问结点的后继直到后继为空时结束。但是，但是，在线索化二叉树中，并不是每个结点都能直接找到其 后继的，当标志为0时，R_child=右孩子地址指针，并非后继 ！需要通过一定运算才能找到它的后继。以中序线索二叉树为例： 对叶子结点（RTag=1），直接后继指针就在其rchild域内； 对其他结点（RTag=0），直接后继是其右子树最左下的结点 ； （因为中序遍历规则是LDR，先左再根再右先左再根再右） 6程序注解 (非递归，且不用栈）： P=T-lchild; /从头结点进入到根结点； while( p!=T)while(p-LTag=link)p=p-lchi
3、ld; /先找到中序遍历起点if(!visit(p-data) return ERROR; /若起点值为空则出错告警while(p-RTag=Thread ) p=p-rchild; Visit(p-data);/若有后继标志，则直接提取p-rchild中线索并 访问后继结点； p=p-rchild; /当前结点右域不空或已经找好了后继，则一律从 结点的右子树开始重复 的全部过程。 Return OK;线索二叉树的中序遍历算法（算法6.5, 参见教材P134）LTag=0RTag=17算法流程：return OK;p=T-lchild;p!=Tp-LTag=0p=p-lchild;vist(p
4、-data);p-LTag=1visit(p-data);p=p-rchild;YNYNYN演 示 程 序8本章小结本章小结1、定义和性质2、存储结构3、遍历4、线索化：线索树顺序结构链式结构二叉链表三叉链表先序线索树中序线索树后序线索树树二叉树森林中序遍历后序遍历先序遍历霍夫曼树霍夫曼编码96.4 树和森林1. 树和森林与二叉树的转换2. 树和森林的存储方式3. 树和森林的遍历101. 树和森林与二叉树的转换转换步骤： step1: 将树中同一结点的兄弟相连; step2: 保留结点的最左孩子连线，删除其它孩 子连线； step3: 将同一孩子的连线绕左孩子旋转45度角 。加线抹线旋转讨论1
5、：树如何转为二叉树？11方法：加线抹线旋转 abeidfhgc树转二叉树举例：abeidfhgc兄弟相连长兄为父孩子靠左根根结点肯定结点肯定 没有右孩子没有右孩子 ！12讨论2：二叉树怎样还原为树？abeidfhgc要点：把所有右孩子变为兄弟！ abeidfhgc13法一： 各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。讨论3：森林如何转为二叉树？法二：森林直接变兄弟，再转为二叉树（参见教材P138图6.17，两种方法都有转换示意图）即F=T1, T2, ,Tm B=root, LB, RB14ABCDEFGHJIABCDEFGHJIA ABCDEFGHJI森林转二叉树举例：（法二
6、）兄弟相连 长兄为父 孩子靠左 头根为根 A A15讨论4：二叉树如何还原为森林？要点：把最右边的子树变为森林，其余右子树变为兄弟 ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B=root, LB, RB F=T1, T2, ,Tm162. 树和森林的存储方式树有三种常用存储方式： 双亲表示法 孩子表示法 孩子兄弟表示法 1、用双亲表示法来存储思路：用一组连续空间来存储树的结点，同时在每个 结点中附设一个指示器，指示其双亲结点在链表中的 位置。parentsdata结点结构dataparents1树结构 23n17A AB BC CGGE EI ID DHHF F缺点：求结点
7、的孩子时需要遍历整个结构。0 1 2 3 4 5 6 7 81 2 2 3 3A B C D E F G H I-1 0 0 1例1: 双亲表示法18思路：将每个结点的孩子排列起来，形成一个带表头 （装父结点）的线性表（n个结点要设立n个链表）； 再将n个表头用数组存放起来，这样就形成一个混合 结构。 例如： abecdfhgdefghgfedcbah123456782、用孩子表示法来存储bc19思路：用二叉链表来表示树，但链表中的两个 指针域含义不同。 左指针指向该结点的第一个孩子； 右指针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild3、用孩子兄弟表示法来存
8、储指向左孩子指向右兄弟20abecdfhgbacedfgh问：树转转二叉树的“连线抹线旋转” 如 何由计算机自动实现？ 答：用“左孩子右兄弟”表示法来存储即可 。存储的过程就是转换的过程！存储的过程就是转换的过程！例如：213、树和森林的遍历先序遍历 C 访问根结点； C 依次先序遍历根结点的每棵子树。树的遍历树的遍历例如：abdec先序序列： 后序序列：a b c d e b d c e a 后序遍历 F依次后序遍历根结点的每棵子树； F访问根结点。树没有中序遍历（因子树不分左右）遍历深度遍历（先序、中序、后序 ） 广度遍历（层次）22讨论：若采用“先转换，后遍历”方式，结果是否一样？abd
9、ec先序遍历：后序遍历：中序遍历：d e c b aabdeca b c d eb d c e a1. 树的先序遍历二法相同； 2. 树的后序遍历相当于对应二叉树的中序遍历； 3. 树没有中序遍历，因为子树无左右之分。结论：23 先序遍历 F若森林为空，返回； F访问森林中第一棵树的根结点； F先序遍历第一棵树中根结点的子树森林； F先序遍历除去第一棵树之后剩余的树构成的森林 。 中序遍历 F若森林为空，返回； F中序遍历森林中第一棵树的根结点的子树森林； F访问第一棵树的根结点； F中序遍历除去第一棵树之后剩余的树构成的森林 。森林的遍历ABCDEFGHJI24讨论：若采用“先转换，后遍历”
10、方式，结果是否相同？例如：A AB BC CD DE EF FGGHHJ JI I先序序列：中序序列：A B C D E F G H I JB C D A F E H J I GA AB BC CD DE EF FGGHHJ JI I先序序列：中序序列：A B C D E F G H I JB C D A F E H J I G结论：森林的先序和中序遍历在 两种方式下的结果相同。 （但森林的后序遍历则不一定）25本章小结本章小结1、定义和性质2、存储结构3、遍历4、线索化：线索树顺序结构链式结构二叉链表三叉链表先序线索树中序线索树后序线索树树树二叉树二叉树森林森林先 序 遍 历后 序 遍 历遍历存储结构遍历双亲表示孩子表示孩子兄弟先序遍历后序遍历中序遍历后序遍历先序遍历霍夫曼树霍夫曼编码26
