大三上复习数据结构第五章

1、第 五 章树和二叉树主要内容：一、树的基本概念二、二叉树三、树与森林四、哈夫曼树华南师范大学 地理科学学院 罗文斐树型结构是一种重要的非线性结构，它可以用来描述客观世界中广泛存在的层次和分支关系。华南师范大学 地理科学学院 罗文斐一、树的基本概念1. 树的定义例如：家族谱系图树根A子树CDBE叶子FGHIJKLM试用树表示从你的祖父起的家族成华南员师范关大学系地理科学学院 罗文斐ACDBEFGHIJ树的递归定义KLM具有0个结点的树称为“空树”；在任意一棵非空树中：Ø 有且仅有一个特定的称为根(root)的结点；Ø 当n>1时，其余结点可分为m(m>0)个互不相

2、交的有限集T1，T2，Tm，其中每一个集合本身又是一 棵树，称为根结点的子树(subtree)。华南师范大学 地理科学学院 罗文斐ACDB树的特点在任意一棵非空树中：EFGHIJKLMØ 存在唯一的一个没有前驱的结点，称它为树的根；Ø 除根以外，集合中的每个结点都有且仅有一个前驱；Ø 所有结点都可以有任意个后继（包括0）；华南师范大学 地理科学学院 罗文斐思考：下图那棵不是树，为什么？AADBBCDEFHIJEFHIJLM华南师范大学 地理科学学院 罗文斐A2. 基本术语CDBEFGHIJq 根结点KLM根为树中唯一的没有前驱的结点。q 度（结点的度和树的度）一个

3、结点的子树的数目，称为结点的度。即后继结点的个数树中结点的度的最大值，称为树的度。q 叶子结点度为0的结点，称为叶子结点，也称终端结点。华南师范大学 地理科学学院 罗文斐ACDBEFGHIJq 分支结点(非终端结点)度不为0的结点。KLM在分支结点中，除了根节点，其余的又称“内部结点”q 双亲结点、孩子结点、兄弟结点、堂兄弟结点某结点的前驱结点称为该结点的双亲结点。某结点的子树的根结点，称为孩子结点。（后继结点）同属于一个双亲的孩子结点互为兄弟结点。其双亲结点为兄弟的结点互为堂兄弟结点。华南师范大学 地理科学学院 罗文斐ACDBEFGHIJKLMq 路径、路径长度一个从a0到am所经过的结点序

4、列（a0，a1，am）称为一条由a0到am的路径，其中（ai-1，ai）满足前驱后继关系。路径中经过的边数称为路径长度。q 祖先和子孙从x到y有一条路径，x称为y的祖先；y称为x的子孙华南师范大学 地理科学学院 罗文斐ACDBEFGHIJKq 结点的层次、树的深度（高度）LM根的层次为第一层，根的孩子为第二层。一个结点的层次为L，则其孩子的层次为L+1。树中结点的最大层次，称为树的深度或高度。华南师范大学 地理科学学院 罗文斐结点A的度： 结点B的度： 结点M的度：叶子结点：结点I的双亲： 结点L的双亲：结点A的孩子： 结点B的孩子：A结点B、C、D为结点K、L为BCDEFGHIJ树的度：树的

5、深度：KLM结点A的层次： 结点M的层次：结点F、G互为结点A是结点F、G的华南师范大学 地理科学学院 罗文斐q 有序树、无序树若将树中结点的各子树看成是自左向右有次序的（即不能交换），则称该树为有序树，否则称为无序树。有序树最左边的孩子称为第一个孩子，最右边为最后一个孩子A最后1个孩子D第1个孩子BCEFGHIJKLM华南师范大学 地理科学学院 罗文斐q 层序编号按照从上到下、从左到右的顺序，从自然数1开始，依次给树的结点进行编号，这个编号成为“层序编号”1A234CDB567 GEF8 H9I10J11K12L13 M华南师范大学 地理科学学院 罗文斐q 森林多棵不相交的树的集合，称为“森

6、林”CDBEFGHIJKLM华南师范大学 地理科学学院 罗文斐补充：森林与树的相互关系树是一个特殊的森林（森林中只有一棵树）一棵树去掉根节点之后，剩下的若干棵子树又组成森林A树=根结点+子树森林CGDIBEFHJMKL华南师范大学 地理科学学院 罗文斐二、二叉树1.二叉树的概念定义：二叉树是n(n³0)个结点的有限集，它或者为空树（空二叉树），或者由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。q华南师范大学 地理科学学院 罗文斐q 特点Ø 每个结点至多有二棵子树(即结点的度不会超过2)。Ø 二叉树的子树有左、右之分，且其次序不能任意颠倒。即使只有

7、一棵子树，也必须区分是左子树还是右子树注：二叉树和树是两种不同的树型结构，二叉树不等同于度为2的有序树。例如，如果根结点只有一棵子树，那么对树而言，它就是一个“独生子”，无左右之分，但对二叉树 而言，必须明确区分它是左子树还是右子树，两者将构成不同的二叉树。AAABBCB左子树右子树华南师范大学 地理科学学院 罗文斐二叉树的5种基本形态P.123图6.3：AAFAABCBB只有根结点的二叉树左、右子树均非空空二叉树右子树为空左子树为空华南师范大学 地理科学学院 罗文斐华南师范大学 地理科学学院 罗文斐任何形态的二叉树都可由5种基本形态（递归）组成ABCDEACBDEFGH南师范大学 地理科学学

8、院 罗文斐2. 特殊的二叉树 P.124（1）满二叉树每个分支结点都存在（非空的）左、右子树，所有的叶子结点都在同一层上1213234567456789华南师范大学 地理科学学院 罗文斐特点：在满二叉树中，每个结点的度只有0和2，叶子结点只能出现在最下面的一层上。12345第三层67华南师范大学 地理科学学院 罗文斐（2）完全二叉树112323456745完全二叉树6满二叉树对完全二叉树和一棵具有相同深度的满二叉树的每个结点进行层序编号，如果两棵树相同位置的结点层序编号都相同，称为“完全二叉树”。华南师范大学 地理科学学院 罗文斐1112323234465554完全二叉树直观解释：完全二叉树“

9、所去掉的结点”总是满二叉树中最后若干个结点判断P.125图6.4完全二叉树的特点是：（1） 所有的叶结点都出现在第k层或k1层。（k为最大层）（2） 对任一结点，如果其右子树的最大层数为L，则其左子树的最大层数为L或L1。非完全二叉树非完全二叉树华南师范大学 地理科学学院 罗文斐华南师范大学 地理科学学院 罗文斐3. 二叉树的性质性质1： 在二叉树的第i层上至多有2i-1个结点(i>=1)。采用归纳法证明:当i=1时，只有一个根结点，2i-1=20=1,命题成立。假设所有的j，1<=j<=i-1,命题成立，即第j层上至多有2j-1个结点，往证：第i层上最多有2i-1个结点。由

10、归纳假设可知，第i1层上至多有2i-2个结点。因为二叉树每个结点的度最大为2，故在第i层上最大结点数为第i1层上最大结点数的二倍，即2×2i-22i-1。命题得到证明。思考：在什么情况下每i层都达到2i-1最大的结点数？华南师范大学 地理科学学院 罗文斐性质2：深度为k的二叉树至多有2k1个结点（k>=1)根据性质1得到每层上的最大结点数进行计算。性质3：对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0n21。证明：令二叉树中度为1的结点数为n1，二叉树中总结点数为N。有：Nn0n1n2（二叉树由度为0、1、2的结点组成）度为1的结点有一个孩子，度为2的结

11、点有两个孩子： 所有孩子结点总数为：n12n2 (注意这些结点都具有双亲结点)（后续）华南师范大学 地理科学学院 罗文斐（续）证明：令二叉树中度为1的结点数为n1，二叉树中总结点数为N。有：Nn0n1n2度为1的结点有一个孩子，度为2的结点有两个孩子：所有孩子结点总数为：n12n2在二叉树中，除了根不是孩子结点，因此，所有结点总数为：得：N=1n12n2n0n1n2 1n12n2123有：n0n21456华南师范大学 地理科学学院 罗文斐性质2：深度为k的二叉树至多有2k1个结点（k>=1)性质4：具有n个结点的完全二叉树的深度为ëlog2nû 1。符号x表示不大于x

12、的最大整数。相当于int(x)假设此二叉树的深度为k，则根据性质2及完全二叉树的定2k-1 2k-1<2k义得到：n（即不超过k满二叉树，而大于k-1满二叉树）11223345467华南师范大学 地理科学学院 罗文斐求证：具有n个结点的完全二叉树的深度k为ëlog2nû 1。2k-12k-1 2k-1<2k<2knn取对数得到：k1 log2nlog2n<kklog2n+1且k>因为(深度)k是整数。所以有：k ëlog2nû1。小数整数整数小数log2nlog2n+1log2nlog2n+1华南师范大学 地理科学学院 罗文

13、斐性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log2n+1层，每层从左到右),则对任一结点i（1<=i<=n),有：（1） 如果i1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点i/2，相当于int(i/2)。（2） 如果2in，则结点i的左孩子编号是2i;如果2i>n， 结点i为叶子结点，无左孩子（意味着也没有右孩子）。12345华南师范大学 地理科学学院 罗文斐（3）如果2i1n，则结点i的右孩子是结点2i1；否则无右孩子。（2）、（3）的总结：在完全二叉树中，i结点的左孩子结点编号为2i（如果2in），右孩子结点的编号为2i

14、+1（如果2i+1n）;i结点如果没有左孩子（2i>n），必为叶子结点，作为叶子结点i的判断条件。12345华南师范大学 地理科学学院 罗文斐对（2）、（3）的证明思路（从2、3可以导出1）：证明第一层（i1）成立证明（任意）第j层成立对第j层所有位置i进行数学归纳法证明i证明i为第j层第1个结点成立在第j层任意位置上假定第i位置成立i+1成立ii+1如果第i位置为j层最后一个结点，需要特殊处理华南师范大学 地理科学学院 罗文斐性质2：深度为k的二叉树至多有2k1个结点对（2）、（3）的证明：采用归纳法证明，i=1时，左孩子为2，右孩子为3 如果i结点是任意j层的第1个结点，有i=2j-

15、1它的左孩子必定是第j+1层第一个结点，右孩子为第二个结点第j+1层第一个结点编号为：2j，即2i，第二个结点为2i1 考虑i结点的任意情况，假设i结点的左孩子编号是2i，右孩子编号是2i+1成立。往证：第i+1个结点的左孩子编号为2(i+1)，右孩子为2(i+1)+1i/2ii兄弟i+1i+1堂兄弟2i2i+12(i+1)2i+32i2i+12(i+1)2i+3当i和i+1结点在同一层华南师范大学 地理科学学院 罗文斐当i和i+1结点不在同一层这时，i结点为第j层最后一个结点，i+1结点为第j+1层的第一个结点第j层i第j+1层i+12i2i+1第j+2层?两种情况下，第i+1个结点的左孩子

16、编号为2(i+1)，右孩子为2(i+1)+1证毕。华南师范大学 地理科学学院 罗文斐4. 二叉树的抽象数据类型定义P.121123ADT BiTreeData:见二叉树的定义（略） Operation:InitBiTree DestroyBiTree ClearBiTree清空树BiTreeEmpty判断空树BiTreeDepth求树的深度Root返回树根Value返回某个结点的值Assign给某个结点赋值华南师范大学 地理科学学院 罗文斐Parent、LeftChild、RightChild、LeftSibling、RightSibling求结点的双亲、左右孩子以及左右兄弟InsertChi

17、ld（T,p,LR,c）LR0/1，把c插入到T树中p结点的左/右子树，同时 p原来的左/右子树作为c的右子树DeleteChild（T,p,LR）LR=0/1，删除p的左/右子树华南师范大学 地理科学学院 罗文斐SearchBiTree-在树中检索值为x的结点PreOrderTraverse-前(先)序遍历二叉树InOrderTraverse-中序遍历二叉树PostOrderTraverse-后序遍历二叉树LevelOrderTraverse-层序遍历二叉树;ADT BiTree华南师范大学 地理科学学院 罗文斐5. 二叉树的遍历P.128在二叉树的一些应用中，常常要求在树中查找具有某种特征

18、的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径（次序）访问树中的结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是一对多的，因而需要寻找一种规律，以便使二叉树上的结点能排列在某个顺序上，从而实现遍历。华南师范大学 地理科学学院 罗文斐q 如果以L代表左子树，D代表根，R代表右子树，则二叉树的遍历方案可以有六种：DLR、LDR、LRD、DRL、RDL、RLDq 前（根）序遍历（DLR）、中（根）序遍历（LDR）和后（根）序遍历（LRD）DRL华南师范大学 地理科学学院 罗文斐遍历算法前序遍历二叉树的操作定义为：

19、若二叉树为空，则空操作；否则（1）访问根结点；（2）前序遍历左子树；（3）前序遍历右子树。-+/a*feb-cd华南师范大学 地理科学学院 罗文斐中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。-+/a*fe后序遍历二叉树的操作定义为：b-若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。cd自行练习其他二叉树的遍历华南师范大学 地理科学学院 罗文斐6. 二叉树的存储结构（1）顺序存储结构P.126它是用一组连续的存储单元存储二叉树的数据元素。除了把结点存放在数组中，还必须考虑结点之间

20、的逻辑关系。如何表示双亲、左、右孩子、根结点、叶子结点？华南师范大学 地理科学学院 罗文斐满/完全二叉树：按照层序编号存放在数组中1a2b3c4d5e6f12l87g8h10j11k9i12345679101112存储位置蕴含了结点之间的关系（二叉树的性质5） 如：双亲结点左/右孩子结点的关系、根结点、叶子华南师范大学 地理科学学院 罗文斐abcdefghijklØ 表示虚设的结点，并不存在虚结点一般二叉树一般二叉树的存储仍按照完全二叉树的存储方式。虚结点仍保留它的存储位置思考：叶子结点判断是否不同华南师范大学 地理科学学院 罗文斐ABCDEØØØ

21、16;FGGFØØØDØEBCA优缺点： 结点间关系蕴含在其存储位置中。 适合存储满二叉树和完全二叉树，一般二叉树将浪费很多存储空间，特别地，对于k个结点的单枝树，需要长度为2k-1的数组 插入操作不易实现？（需要移动整棵子树的结点）华南师范大学 地理科学学院 罗文斐链式存储结构二叉链表三叉链表线索链表便于遍历（见遍历二叉树）华南师范大学 地理科学学院 罗文斐（2）二叉链表root结点结构：AlchilddatarchildBCDEF结点定义：struct BiTNodeelemtype data;struct BiTNode *lchild，*rchi

22、ld;typedef BiTNode *BiTree ;GH二叉树结构最直观的存储方式华南师范大学 地理科学学院 罗文斐（3）三叉链表二叉链表不便于查找结点的双亲结点三叉链表添加一个指针域，指向其双亲结点root结点结构：AlchildparentdatarchildBCDEFGH华南师范大学 地理科学学院 罗文斐结点结构：结点定义：struct TriTNodedatatype data;struct TriTNode *lchild，*rchild，*parent;Typedef TriTNode *TriTree;华南师范大学 地理科学学院 罗文斐lchildparentdatarchi

23、ld7. 二叉树链式结构的遍历算法(1)遍历的递归算法结点定义：struct BiTNodeelemtype data;struct BiTNode *lchild，*rchild;typedef BiTNode *BiTree ;前序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）前序遍历左子树；（3）前序遍历右子树。遍历的递归算法：void Preorder (BiTree BT)/BT为指向二叉树BT根节点的指针/ 前序遍历以T为根指针的二叉树if (BT!=NULL) visit(BT);/ BT=NULL时，二叉树为空树，不做任何操作/ visit :访问

24、根结点(例如:输出BT->data)Preorder(BT->Lchild); / 前序遍历左子树Preorder(BT->Rchild); / 前序遍历右子树 / if见P.129算法6.1(只是多了一些判断，这里为了更加清楚表达思路，省略了这些 判断)华南师范大学 地理科学学院 罗文斐其它遍历的递归算法类似写出三种遍历的递归算法华南师范大学 地理科学学院 罗文斐前序遍历二叉树Preorder( BiTree BT )中序遍历二叉树InOrder( BiTree BT )后序遍历二叉树PostOrder( BiTree BT )若二叉树为空，则空操作； 否则(1) 访问根结

25、点；(2) 前序遍历左子树；(3) 前序遍历右子树。若二叉树为空，则空操作；否则(1) 中序遍历左子树；(2) 访问根结点；(3) 中序遍历右子树。若二叉树为空，则空操作；否则(1) 后序遍历左子树；(2) 后序遍历右子树；(3) 访问根结点。*(2)遍历的非递归算法q 前序遍历算法q 中序遍历算法q 后序遍历算法q 层次遍历算法（课后思考）华南师范大学 地理科学学院 罗文斐*中序遍历8105911167324先走最左边的路径：（ 8 ,5 ，1，3，2 ）分别访问：2 (右子树) 、3右子树、1(右子树)、5右子树、8 右子树华南师范大学 地理科学学院 罗文斐voidinorder(BiTr

26、ee T)InitStack(S);p=T;while( !StackEmpty(S) | p )if(p)Push( S , p );p=p->lchild;/结点压栈/一直走到最左端else/表示左子树已经遍历完了Pop( S , p ); visit( p ); /弹出结点，访问该结点p = p->rchild; /然后开始访问其右子树/课本P.131算法6.3，比较算法6.2华南师范大学 地理科学学院 罗文斐华南师范大学 地理科学学院 罗文斐*前序遍历8105911167324先访问最左边的路径： 8 ,5 ，1，3，2再访问：(2的右子树) 、3的右子树、(1的右子树)、

27、5的右子树、8的右子树华南师范大学 地理科学学院 罗文斐voidpreorder(BiTree bt)BiTree p=bt, sM;while(p)int top=-1;往左下方向走，同时把沿路的非空右孩进栈。while(p)visit(p);if(p->rchild)s+top=p->rchild;/右子树入栈某结点的左子p=p->lchild;树已被遍历；现在准备遍历其右子树。if(top>=0)p=stop-;/最后访问的根节点的右子树最先被访问华南师范大学 地理科学学院 罗文斐前序遍历算法(3)遍历算法的应用q 建立二叉树（递归方法）,作业：理解课本P.131

28、算法6.4q 求二叉树的深度q 对二叉树中结点的检索华南师范大学 地理科学学院 罗文斐(4)线索链表通过二叉树的遍历，可以把二叉树的结点排成一个线性序列。在应用中，有时 给定一个结点，来查找该结点在这个序列中的前驱和后继。一种简单的做法是：在遍历过程中，把遍历的结点逐个记录在一个线性表当中，或者在结点中增加前驱或后继的指针域。这样需要浪费很多的存储空间。事实上，能否充分利用二叉链表的存储空间来存放这种遍历顺序？华南师范大学 地理科学学院 罗文斐思考：在有n个结点的二叉链表中，有几个空链域？因此，能否利用这些指针域来存放 “特殊的”指针，用于指向该结点在某种遍历序列中前驱或后继结点？AGCEF华

29、南师范大学 地理科学学院 罗文斐线索二叉树的有关概念p 线索：在结点指针域中，专用于指向 在某个遍历顺序中，某结点的前驱或后继的指针称为线索。p 线索二叉树（ Threaded Binary Tree ）：加上线索的二叉链表表示的二叉树叫线索二叉树。p 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。华南师范大学 地理科学学院 罗文斐lchildltagdatarchildrtag实现方法在二叉链表的每个结点中增加两个标志域：ltag：若ltag=0，lchild域指向左孩子；若ltag=1，lchild域指向其前驱（原来的空指针域）。rtag：若rtag=0，rchild域

30、指向右孩子； 若rtag=1，rchild域指向其后继。即：当结点有左或右孩子时，tag=0，对应指针域指向的是孩子结点如果没有左或右孩子时，tag=1，对应指针域指向的是前驱或后继注：标注域比指针域省空间华南师范大学 地理科学学院 罗文斐如何查找中序线索链表中某结点的前驱和后继rootABCEF后继：右子树空的结点（B）后继是A线索右子树非空的结点（A）后继右子树最左边的结点前驱：左子树空的结点（E）前驱是A线索左子树非空的结点（A）前驱左子树最右边的结点华南师范大学 地理科学学院 罗文斐课后尝试写出以下两个算法NextNode_Inorder( BiThrTree p )/求p的后继结点P

31、reviousNode_Inorder( BiThrTree p )/求p的前驱结点*遍历线索二叉树的有关操作q 找线索二叉树按某种遍历顺序的前驱和后继，有一半结点可以直接找到，另一半结点仍要根据树中结点的关系去查找。P.134算法6.5：中序遍历线索二叉树（非递归）华南师范大学 地理科学学院 罗文斐华南师范大学 地理科学学院 罗文斐线索化算法主要思想：进行中序遍历，并在遍历的过程中，如果遇到空的左指针，令该指针指向前驱，如是空的右指针则指向后继，同时将相应的ltag和rtag的值置为1。q 中序线索化核心算法：P.135算法6.7 (见下一页)(算法6.6为总流程)华南师范大学 地理科学学院

32、 罗文斐void InThreading(BiThrTree p)/遍历的同时,对树进行线索化（算法6.7）/p为当前访问的结点,pre为刚刚访问的结点(可定义为全局变量)if(p)InThreading( p->lchild );/对左子树线索化（遍历）/建立线索/(pre记录了遍历左子树的最后一个结点),pre与p构成了前驱和后继if( p->lchild = NULL ) p->LTag = 1; p->lchild = pre; /p左子树为空,则其前驱为pre（刚刚被访问的结点）if( pre->rchild = NULL ) pre->RTag

33、= 1; pre->rchild = p; /如果pre的右子树为空，则它的后继应该为ppre = p;/当前p结点处理完毕,因此刚刚访问完毕的pre=p InThreading( p->rchild );/对右子树线索化/理解蓝色字体部分课后阅读P.134算法6.6，理解else部分（结合InThreading），思考最后一个 结点的处理 提示：该部分是线索化过程的完整内容华南师范大学 地理科学学院 罗文斐华南师范大学 地理科学学院 罗文斐三、树与森林1. 树的抽象数据类型（操作部分）P.118119InitTree DestroyTree Root-求树根Parent-求结点x

34、的双亲Children-依次输出结点x的孩子（个数任意） PreOrder-前序遍历树TraverseTreePostOrder-后序遍历树LeverOrder-层序遍历树华南师范大学 地理科学学院 罗文斐2. 树的存储结构（1）双亲表示法（顺序存储结构）结点结构结点的数据域双亲结点的位置华南师范大学 地理科学学院 罗文斐dataparentDataParent(双亲结点的index)索引012345678-1表示无双亲ACBGHEDFI特点：找双亲容易，找孩子慢。如何找孩子？试编写算法,分析时间复杂度华南师范大学 地理科学学院 罗文斐A-1B0C0D1E1F1G2H2I4（2）孩子表示法q

35、多重链表：包括一个数据域和多个指针域（指向多个孩子）q 其中，“多个指针域”采用顺序存储结构表示单个结点见课本P.136图（上图）每个结点的 指针域个数不定，如何处理？方法一：静态数组，数组长度为整棵树的度（浪费空间、被限制）上图方法二：结点度动态数组（不方便）下图这种表示法是表示树最直观的方法但不灵活华南师范大学 地理科学学院 罗文斐datachild1child2.child nq 孩子链表：使用单链表来存放其孩子结点的信息使用两个结构：树结点结构单链表结点结构结点的数据域指向孩子链表的头 孩子结点的位置结点华南师范大学 地理科学学院 罗文斐childnextdatafirstchild顺

36、序存储结构单链表结构datafirstchild索引0123456AC123数组索引BD45EF6特点：找孩子容易，找双亲更难。G如何找双亲？树结点结构（顺序存储）华南师范大学 地理科学学院 罗文斐ABCDEFG（3）孩子双亲表示法结合孩子表示法与双亲表示法两种方法AC0123456123BD45EF6G华南师范大学 地理科学学院 罗文斐A-1B0C0D0E2F2G4（4）孩子兄弟表示法：二叉链表存储法每个结点存储第一个孩子的指针以及第一个右兄弟的指针ABCDE思考：如何找孩子华南师范大学 地理科学学院 罗文斐EDCBAfirstchilddatarightsib3. 树、森林与二叉树的转换A

37、ABBCD等价CEED树可借助二叉树存储华南师范大学 地理科学学院 罗文斐EDCBA树到二叉树的转换AAACBBCDBDCE调整DE加线（兄弟线）E抹线（双亲线）第一个孩子除外华南师范大学 地理科学学院 罗文斐二叉树到树的还原AAABBCDBCCEE抹线DE加线D调整结点的左孩子的右链上所有结点与该结点相连抹掉该孩子结点与右链结点的连线华南师范大学 地理科学学院 罗文斐森林到二叉树的转换(画法)见P.138图6.17(1) 转换将森林中每棵树转换成二叉树(2) 连线，从左到右，把每棵二叉树的根节点作为前一棵二叉树根节点的右子树(3) 调整位置二叉树到森林的转换（画法）(1)抹线抹掉二叉树根节点

38、(A)右链上的所有连线(2)还原对各自的子二叉树还原为树(3)调整思考：森林对应的二叉树与一棵树对应的二叉树有什么不同特征？华南师范大学 地理科学学院 罗文斐华南师范大学 地理科学学院 罗文斐森林与二叉树转换的递归算法P.138F = ( T1, T2, , Tn );把森林分为三个部分rootBE t11KT1DICGFHJMt12LT2T3华南师范大学 地理科学学院 罗文斐二叉树B =( LBT, Node(root), RBT );DLBTRBT华南师范大学 地理科学学院 罗文斐由森林转换成二叉树的转换规则为:若 F = ，则 B = ;否则，rootDLBTRBTDICGBE t11K

39、T1FHJMt12LT2T3由 ROOT( T1 ) 对应得到Node(root);由 (t11, t12, , t1m ) 转换为 LBT;由 (T2, T3, Tn )转换为 RBT。华南师范大学 地理科学学院 罗文斐由二叉树转换为森林的转换规则为:若 B = , 则 F = ;否则，由 Node(root) 对应得到 ROOT( T1 );由LBT 转化为T1的 ( t11, t12, ，t1m);由RBT 继续转化为 (T2, T3, , Tn)。华南师范大学 地理科学学院 罗文斐4. 树与森林的遍历Aq 树的层序遍历q 树的前/先序遍历BCDq 树的后序遍历GEFHJKLMI树遍历过

40、程的定义P.138前/先序遍历： AB E F INOG C D HJ KL NOM 后序遍历： E I F G B C J K N O L M H D A层序遍历： AB C D E F GH I J KL MN O华南师范大学 地理科学学院 罗文斐华南师范大学 地理科学学院 罗文斐树遍历的实现可先转换成二叉树，然后用二叉树的遍历算法来实现二叉树的遍历与树遍历的对应关系： 树的前序遍历与二叉树的前序遍历对应A 树的后序遍历与二叉树的中序遍历对应A 树的层次遍历没有对应B利用P.137图6.6验证BCDCEDE华南师范大学 地理科学学院 罗文斐森林的遍历P.139森林遍历把森林划分为3个部分，

41、以第一棵树的根节点作为根（1）前序遍历（递归）：访问森林中第一棵树的根节点前序遍历第一棵树除了根节点后剩下的子树森林前序遍历除了第一棵树外，剩余树构成的森林利用树的遍历来实现：依次从左至右对森林中的每一棵树进行 前序遍历。思考：P.138图6.17森林的前序遍历转化为二叉树的遍历来实现：二叉树的前序遍历。华南师范大学 地理科学学院 罗文斐（2）中序遍历（递归）：中序遍历第一棵树除了根节点后剩下的子树森林访问第一棵树的根节点中序遍历除了第一棵树后，剩余树构成的森林利用树的遍历来实现：依次从左至右对森林中的每一棵树进行后序遍历。转化为二叉树的遍历来实现：二叉树的中序遍历。课后练习：以一个森林为例，试写出各种遍历的结果华南师范大学 地理科学学院 罗文斐 对应关系树森林二叉树前序遍历前序遍历前序遍历中序遍历中序遍历后序遍历华南师范大学 地理科学学院 罗文斐四、哈夫曼树考虑电文的二进制编码问题：需传送的电文为“ABACCDA”，如何进行二制编码，使得编码总长度最短？方案1：分别用00、01、10和11为A、B、C和D编码。结 果：能