数据结构教程第6单元-树和二叉树(新)

1、数据结构教程7 树和二叉树授课老师：彭伟国计算机学院 7 树和二叉树 7.1 树的基本概念 7.2 二叉树概念和性质 7.3 二叉树存储结构 7.4 二叉树的基本运算及其实现 7.5 树与森林 7.6 二叉树的遍历及构造 7.7 线索二叉树 7.8 哈夫曼树 树的定义与基本术语二叉树的特性(重点)二叉树的存储结构(重点)二叉树的遍历(重点)线索二叉树树和森林与二叉树的转换(重点)最优树和哈夫曼编码(重点)主要内容掌握树的基本定义及其相关的术语的含义；熟练掌握二叉树的结构特性，了解相应的证明方法 ；熟悉三种遍历二叉树的递归算法；理解二叉树线索化的实质及线索化的过程；掌握树、森林与二叉树的转换及其

2、各自遍历的对应关系；掌握哈夫曼编码的原理及实现方法。 教学要求教学重点： 二叉树的定义和逻辑特点，二叉树的链式存储结构的组织方式，二叉树的三种遍历方法及其算法，一般树转化为二叉树的方法，哈夫曼树及哈夫曼编码，哈夫曼编码的应用。 教学难点： 二叉树的递归定义，二叉树链式存储结构的组织方式，三种遍历的区别，哈夫曼编码。教学重点及难点一、树的定义 定义：树(Tree)是n(n=0)个结点的有限集T，n=0时称为空树，否则对任意一棵非空树，它满足如下两个条件：ACGBDEFKLHMIJ（1）有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m0)个互不相交的子集T1,T2,T3T

3、m，其中每个子集又是一棵树，并称其为根的子树(Subtree)。树的定义是采用递归方法7.1 树的定义和基本术语树的应用举例文件结构My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic7.1 树的定义和基本术语图示法、集合（文氏）法、凹入法、广义表法树的表示方法：A B C D E F G ADBCEFGABCDEFG每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。是一种分支的、层次的结构ACGBDEFKLHMIJ二、树的特点7.1 树的定义和基本术语三、树的基本术语结点的度：结点所拥有的子树的个数。树的度：树中各结点度的最

4、大值。CGBDEFKLHMIJA7.1 树的定义和基本术语三、树的基本术语叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。CGBDEFKLHMIJA7.1 树的定义和基本术语三、树的基本术语孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；兄弟：具有同一个双亲的孩子结点互称为兄弟。 CGBDEFKLHMIJA7.1 树的定义和基本术语三、树的基本术语路径：如果树的结点序列n1, n2, , nk有如下关系：结点ni是ni+1的双亲（1=i=0)个结点的有限集合，此集合或者为空集（n=0），或者由一个根结点及两棵互不相

5、交的左右子树组成，并且左右子树都是二叉树。123485679107.2.1 二叉树的定义二、二叉树的特点 1.每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点); 2.该两棵子树可以为空; 3.该两棵子树有次序之分，分别称之为左子树和右子树,其次序不能任意颠倒。12348567910ABAB7.2.1 二叉树的定义二叉树的五种不同形态 (a)空二叉树 (b)仅有根结点的二叉树 (c)右子树为空的二叉树L (d)左子树为空的二叉树R (e)左、右子树均非空的二叉树LR三、二叉树的基本形态7.2.1 二叉树的定义二叉树与树的区别：A树中结点的最大度数没有限制，二叉树结点最大度数为2。B树的

6、每个结点的子树无左、右之分，二叉树的结点子树有明确的左、右之分。二叉树与有序树的区别：C.在有序树中，某个结点只有一个孩子时就无左、右之分 特别要注意：二叉树不是树的特殊情况，它们是两种不同的树型结构。四、二叉树与树和有序树的区别7.2.1 二叉树的定义练习：画出含有3个结点的树与二叉树的所有不同形态 树 二叉树斜树1 .所有结点都只有左子树的二叉树称为左斜树2 .所有结点都只有右子树的二叉树称为右斜树3.左斜树和右斜树统称为斜树。1. 在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。 斜树的特点：ABCABC特殊的二叉树满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉

7、树。 特点：123485679101112131415叶子只能出现在最下一层；只有度为0和度为2的结点。特殊的二叉树不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多A1523467BCDEFGLM89特殊的二叉树完全二叉树-深度为k的，有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树（也称为近似满二叉树） 完全二叉树12348567910特点：（1）叶子结点只可能在层次最大的两层上出现 （2）对任一结点，若其右分支下的子孙最大层次为L，则

8、其左分支下的子孙最大层次必为L或L+1123485679101112131415特殊的二叉树12345612345721367(a)完全二叉树(b)非完全二叉树( c)非完全二叉树满二叉树是完全二叉树的特例。特殊的二叉树由此可得出如下结论：对一棵完全二叉树，有： 1.至多只有最下面两层上结点的度数可以小于2 2.最下面一层结点都集中在该层的最左边 3.满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。12348567910特殊的二叉树性质1：在二叉树的第i层上至多有2i-1个结点证明： 用数学归纳法。 1) 当i

9、=1时，整个二叉树只有一根结点，此时2i-1=20=1，结论成立。 2) 设i=k时结论成立，即第k层上结点总数最多为2k-1个。 现证明当i=k+1时， 结论成立。 因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即22k-1=2 (k+1)-1，故结论成立。 GKJCFABEIHD度为m的树中第i层上至多有mi-1个结点, (i1)。7.2.2 二叉树的性质性质2：任何一棵二叉树中度为2的结点数目n2比度为0的结点数目n0少1，即n2 n0-1。 证明：设二叉树中结点总数为n，n1为二叉树中度为1的结点总数，设二叉树中分支数目为B 。 n=n0+n1

10、+n2 除根结点外，每个结点均对应一个进入它的分支： n=B+1 二叉树中的分支都是由度为1和度为2的结点发出 B=n1+2n27.2.2 二叉树的性质性质3：深度为k的二叉树至多有2k-1个结点 证明：因为深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数至多为（性质1） 深度为k的m叉树至多有 个结点。7.2.2 二叉树的性质提问：深度为k时至少有 个结点？k性质4：具有n个结点的完全二叉树的深度为 符号 表示不大于x的最大整数。12348567910完全二叉树的两个重要特性7.2.2 二叉树的性质证明：设n个结点的完全二叉树的深度为k，根

11、据性质2 有 2k-1-1n2k-1 可得 2k-1n 2k， 即 k-1log2n k 因为k是整数，所以k-1=log2n，k= log2n+1,故结论成立。 2k-1n+12k k-1 log2(n+1) k k= log2(n+1)7.2.2 二叉树的性质性质5： 如果对一棵有n个结点的完全二叉树的结点按层次编号,则对编号为i的结点（1=i1，则其双亲是结点i / 2。（2）如果2in，则结点i为叶子结点，无左孩子； 否则，其左孩子是结点2i。（3）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。12348567910完全二叉树的两个重要特性性质5表明，在完全二叉树中，结点

12、的层序编号反映了结点之间的逻辑关系。1 由个结点所构成的二叉树有 种形态。 2. 一棵深度为6的满二叉树有 个分支结点和 个叶子。注：满二叉树没有度为1的结点，所以分支结点数就是度为2的结点数。3 一棵具有个结点的完全二叉树，它的深度为 。 注：用 log2(n) +14、设一棵完全二叉树有700个结点，则共有 个叶子结点。答：最快方法：用叶子数n/2350 概念应用示例概念应用示例5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。答：最快方法：用叶子数n/2500 ，n2=n0-1=499。 另外，

13、最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数0.6. 一棵含有n(n1)个结点的k叉树，可能达到的最大深度为 n ，最小深度为 。答： “完全k叉树”7.3 二叉树的存储结构顺序存储结构二叉树的顺序存储结构就是用一组连续的存储单元存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系父子关系。 如何利用数组下标来反映结点之间的逻辑关系?完全二叉树和满二叉树中结点的序号可以惟一地反映出结点之间的逻辑关系 。7.3 二叉树的存储结构 A B C D E F G H I J数组下标 1 2 3 4 5

14、 6 7 8 9 10完全二叉树的顺序存储CDEFGHIJ以编号为下标完全二叉树7.3 二叉树的存储结构二叉树的顺序存储ABCDEFG数组下标 1 2 3 4 5 6 7 8 9 10 11 12 13ABCDEGF以编号为下标ABCDEGF123561013按照完全二叉树编号一般二叉树7.3 二叉树的存储结构一棵斜树的顺序存储会怎样呢？深度为k的右斜树，k个结点需分配2k1个存储单元。 一棵二叉树改造后成完全二叉树形态，需增加很多空结点，造成存储空间的浪费。二叉树的顺序存储结构一般仅存储完全二叉树ABC137D157.3 二叉树的存储结构二叉链表基本思想：令二叉树的

15、每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。 二叉树的链表表示lChild data rChilddatalChildrChild每个结点由数据域、左指针域和右指针域组成。二叉链表其中，data：数据域，存放该结点的数据信息； lchild：左指针域，存放指向左孩子的指针； rchild：右指针域，存放指向右孩子的指针。 结点结构7.3 二叉树的存储结构GFEDBAABCDEFGC二叉链表具有n个结点的二叉链表中，有多少个空指针？n+1个空指针个数：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+1

16、二叉链表typedef struct BiTnode TElementtype data; struct BiTnode *lchild, *rchild; BiTnode,*BiTree;ABCDEFG AB C D E F Glchilddatarchild在n个结点的二叉链表中，有n+1个空指针域7.3 二叉树的存储结构在二叉链表这种存储结构上，二叉树的多数基本运算如求根、求左、右孩子等很容易实现。但求双亲运算的实现比较麻烦，而且其时间性能较低空间利用不高，在含有n个结点的二叉链表中有n+1个空链域。二叉链表二叉树存储结构课堂练习练习分别画出下图所示二叉树的二叉链表和顺序存储结构示意图A

17、1523467BCDEFGLM897.4.1 二叉树的基本运算概述7.4.2 二叉树的基本运算算法实现7.4 二叉树的基本运算及其实现 归纳起来,二叉树有以下基本运算： (1)创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链式存储结构。 (2)查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。 (3)找孩子结点LchildNode(p)和RchildNode(p)：分别求二叉树中结点*p的左孩子结点和右孩子结点。7.4.1 二叉树的基本运算概述 (4)求高度BTNodeDepth(*b)：

18、求二叉树b的高度。若二叉树为空,则其高度为0；否则,其高度等于左子树与右子树中的最大高度加l。 (5)输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。 (1) 创建二叉树CreateBTNode(*b,*str) 用ch扫描采用括号表示法表示二叉树的字符串。分以下几种情况： 若ch=(：则将前面刚创建的结点作为双亲结点进栈,并置k=1,表示其后创建的结点将作为这个结点的左孩子结点； 若ch=)：表示栈中结点的左右孩子结点处理完毕,退栈； 若ch=,：表示其后创建的结点为右孩子结点；k=2;7.4.2 二叉树基本运算算法实现 其他情况,表示要创建一个结点,并根据k值建立它与栈

19、中结点之间的联系,当k=1时,表示这个结点作为栈中结点的左孩子结点,当k=2时,表示这个结点作为栈中结点的右孩子结点。如此循环直到str处理完毕。算法中使用一个栈St保存双亲结点,top为其栈指针,k指定其后处理的结点是双亲结点(保存在栈中)的左孩子结点(k=1)还是右孩子结点(k=2)。 例如,对于括号表示串A(B(D(,G),C(E,F),建立二叉树链式存储结构的过程如下表所示。ch算法执行的操作St中元素A建立A结点,b指向该结点空(A结点进栈,k=1AB建立B结点,因k=1,将其作为A结点的左孩子结点A(B结点进栈,k=1ABD建立D结点,因k=1,将其作为B结点的左孩子结点ABch算

20、法执行的操作St中元素(D结点进栈,k=1ABD,k=2ABDG建立G结点,因k=2,将其作为D结点的右孩子结点ABD)退栈一次AB)退栈一次A,k=2AC建立C结点,因k=2,将其作为A结点的右孩子结点A(C结点进栈,k=1ACE建立E结点,因k=1,将其作为C结点的左孩子结点AC,k=2ACch算法执行的操作St中元素F建立F结点,因k=2,将其作为C结点的右孩子结点AC)退栈一次A)退栈一次空ch扫描完毕算法结束生成的二叉树 (2) 查找结点FindNode(*b,x) 采用递归算法查找值为x的结点。找到后返回其指针,否则返回NULL。算法如下： BTNode *FindNode(BTN

21、ode *b,ElemType x) BTNode *p; if (b=NULL) return NULL; else if (b-data=x) return b; else p=FindNode(b-lchild,x); if (p!=NULL) return p; else return FindNode(b-rchild,x); (3) 找孩子结点LchildNode(p)和RchildNode(p) 直接返回*p结点的左孩子结点或右孩子结点的指针。算法如下： BTNode *LchildNode(BTNode *p) return p-lchild; BTNode *RchildNo

22、de(BTNode *p) return p-rchild; (4) 求高度BTNodeDepth(*b)求二叉树的高度的递归模型f()如下： f(NULL)=0 f(b)=MAXf(b-lchild),f(b-rchild)+1 其他情况对应的算法如下：int BTNodeDepth(BTNode *b) int lchilddep,rchilddep; if (b=NULL) return(0); /*空树的高度为0*/ else lchilddep=BTNodeDepth(b-lchild);/*求左子树的高度为lchilddep*/ rchilddep=BTNodeDepth(b-rc

23、hild);/*求右子树的高度为rchilddep*/ return(lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); (5) 输出二叉树DispBTNode(*b) 其过程是：对于非空二叉树b,先输出其元素值,当存在左孩子结点或右孩子结点时,输出一个“(”符号,然后递归处理左子树,输出一个“,”符号,递归处理右子树,最后输出一个“)”符号。对应的递归算法如下： void DispBTNode(BTNode *b) if (b!=NULL) printf(%c,b-data); if (b-lchild!=NULL | b-rchild!=NU

24、LL) printf(); DispBTNode(b-lchild);/*递归处理左子树*/ if (b-rchild!=NULL) printf(,); DispBTNode(b-rchild);/*递归处理右子树*/ printf(); 1. 按照二叉树的定义，具有三个节点的二叉树有( )种。A、3 B、4 C、5 D、6 2.若一棵二叉树具有8个叶子结点，6个度为1的结点，则度为2的结点个数是( ) A.5 B.7 C.8 D.93.一棵完全二叉树具有600个结点，则它有( ) 个度为1的结点。A. 25 B. 26 C. 1 D. 0练习1.在具有9个结点的二叉链表中，非空的链域个数为

25、( ) 2.已知完全二叉树的第七层有32个叶子结点，则整个二叉树的结点最多有( 191 )个，最少有（ 95 ）个。3.有100个结点的完全二叉树深度为( 7 ) ；有( 50 ) 个叶子。4.在采用二叉链表结构存储的二叉树中，结点结构为(lchild, data, rchild)，其中lchild和rchild为指针域。指针p所指结点为叶子结点的条件是( lchild和rchild都为空 )7.5 树与森林实现树的存储结构，关键是什么?树中结点之间的逻辑关系是什么?思考问题的出发点：如何表示结点的双亲和孩子如何表示树中结点之间的逻辑关系。7.5.1 树的存储结构父子关系7.5.1 树的存储结

26、构1. 双亲存储结构 这种存储结构是一种顺序存储结构,用一组连续空间存储树的所有结点,同时在每个结点中附设一个伪指针指示其双亲结点的位置。树的双亲存储结构示意图下标 data parent012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 双亲表示法ACBHFEDGI不足：求某结点的孩子结点，即实现Child（t，x，i）操作时，则需要查询整个数组。不能反映各兄弟结点之间的关系，所以实现RightSibling（t，x）操作也比较困难。优点：实现Parent（t，x）操作和Root（x）操作很方便2. 孩子链存储结构 孩子链存储结构可按树的度(即树中所

27、有结点度的最大值)设计结点的孩子结点指针域个数。下图(a)的树对应的孩子链存储结构如图(b)所示。树的孩子链存储结构示意图3. 孩子兄弟链存储结构 孩子兄弟链存储结构是为每个结点设计三个域：一个数据元素域,一个该结点的第一个孩子结点指针域,一个该结点的下一个兄弟结点指针域。下图(a)的树对应的孩子兄弟链存储结构如图(b)所示。树的孩子兄弟链存储结构示意图ACBHFEDGI某结点的第一个孩子是惟一的某结点的右兄弟是惟一的设置两个分别指向该结点的第一个孩子和右邻兄弟的指针 3. 孩子兄弟链存储结构画出下列树的孩子兄弟表示法的结构图(a)(c)树二叉树ABCDEFGABCEDFGAEBCFDG(b)

28、练习7.5.2 树、森林与二叉树的转换借助于“孩子兄弟表示法”实现树与二叉树之间的转化ACBD A B C D=I I J K L=JKL1、树转换为二叉树方法一：借助二叉链表，让该结点的左分枝指向该结点的第一个孩子，右分枝指向该结点的下一个兄弟。ABCDEFGAEBCFDG7.5.2 树、森林与二叉树的转换 I A B C DE F G H(b) A B CDE G H FI(a)ABEFCDGHI(d)ABCDEFGHI(c)方法二： 在树中所有的兄弟结点之间加一连线； 对每个结点，除保留与其长子（最左孩子）的连线外，去除该结点与其它孩子之间的联线； 以根结点为轴心，将整个树顺时针转45度

29、。7.5.2 树、森林与二叉树的转换第一步：在树中所有的兄弟结点之间加一连线第二步：对每个结点，除保留与其长子（最左孩子）的连线外，去除该结点与其它孩子之间的联线；第三步：以根结点为轴心，将整个树顺时针转45度。7.5.2 树、森林与二叉树的转换将下列的树转换为二叉树DIABECFGH转换后的二叉树课堂练习（一）7.5.2 树、森林与二叉树的转换2. 森林转换为二叉树 森林转换为二叉树的方法：将森林中的每一棵树分别转换成二叉树；将各二叉树的根结点视为兄弟用线连起来；以第一棵树的根结点作为二叉树的根结点，按顺时针方向适当旋转。ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBE

30、FHIGJ7.5.2 树、森林与二叉树的转换将如图所示的森林转换为二叉树ADCBEFHIGJ二、二叉树转换成树、森林方法一1.二叉树的根作为森林中第一棵树的根2.二叉树的左子树转换成森林中第一棵树的子树森林3.二叉树的右子树转换成森林中其它的树7.5.2 树、森林与二叉树的转换ADCBEFHIGJEFADCBHIGJADCBEFHIGJ二叉树转换为森林7.5.2 树、森林与二叉树的转换方法二1）将结点的左孩子的右孩子、右孩子的右孩子与该结点连接起来2）去掉所有结点与其右孩子的连线EFADCBEFHIGJADCBHIGJ7.5.2 树、森林与二叉树的转换将如图所示的森林转换为二叉树GHIJLNK

31、OMADCBFE7.5.2 树、森林与二叉树的转换课堂练习将如图所示的森林转换为二叉树GHIJLNKOMADCBFEFADBECGHIJLKOMN课堂练习FADBECGHIJLKOMN最后转换成的二叉树画出下列存储结构对应的二叉树，并将其转换成对应的森林。1234567891011121314ABD0 CEH0000FGIABDCFGEHIBCAHIFEGD课堂练习 7.6 二叉树的遍历及构造7.6.1 遍历二叉树7.6.2 二叉树的构造遍历二叉树遍历定义：遍历用途：遍历方法：指按某条搜索路线遍访每个结点且不重复（又称周游）。它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的

32、基础和核心。对每个结点的查看通常都是“先左后右”。Traversing Binary Tree7.6.1 遍历二叉树层序遍历：按二叉树的层序编号的次序访问各结点。 遍历规则：二叉树由根、左子树、右子树构成，定义为D、 L、R以根结点为参照系注：“先、中、后”的意思是指访问的根结点D是先于子树出现还是后于子树出现。 D、 L、R的组合定义了六种可能的遍历方案：DLR, LDR, LRD, DRL, RDL, RLD 若限定先左后右，则有三种实现方案： DLR LDR LRD先序遍历 中序遍历 后序遍历 先序遍历DLR：访问根结点、先序遍历左子树、先序遍历右子树若二叉树非空 （1）访问根结点； （

33、2）先序遍历左子树； （3）先序遍历右子树；若二叉树为空，结束 基本项（也叫终止项）若二叉树非空 递归项 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；DLR void preorder (BiTNode *root) /先序遍历root指向根的二叉树 if (root!=NULL) coutdata；/访问根结点 preorder(root-Lchild); /先序遍历根的左子树 preorder(root-Rchild); /先序遍历根的右子树 /if /preorder先序遍历LchilddataRchildECDABABCEDrootABCDEFGD L RTD L

34、 RD L RABED L RD L RDLRDLRCFDG先序遍历结果:ABCDEFGT例：对如下二叉树进行先序遍历的结果为ABDCEFFCADEGBABDECFFCADBEG中序遍历LDR：中序遍历左子树、访问根结点、中序遍历右子树若二叉树非空 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树；若二叉树为空，结束 基本项（也叫终止项）若二叉树非空 递归项 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树；DLR void inorder (BiTNode *root) /先序遍历root指向根的二叉树 if (root!=NULL) inorder(root

35、-Lchild); /先序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild); /先序遍历根的右子树 /if /inorder中序遍历LchilddataRchildABCDEFGL D RTL D RL D RABEL D RL D RLDRLDRCFDG中序遍历结果:BDCAGFET例：对如下二叉树进行中序遍历的结果为ABDCEFFCADEGBDBEAFCACBDFEG后序遍历LRD：后序遍历左子树、后序遍历右子树、访问根结点DLR312EGFCDAB后序遍历序列:BDFGECA例：对如下二叉树进行后序遍历的结果为ABDCEFFCADEGBDEBFCA

36、ABDCGEF由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。 先序遍历递归算法： DLR ( BiTree T ) if (T) /非空二叉树 printf(“%d”,T-data); /访问根结点D DLR(T-lchild); /递归遍历左子树 DLR(T-rchild); /递归遍历右子树 return(0); 中序遍历递归算法： LDR(BiTree T) if(T) LDR(T-lchild); printf(“%d”,T-data); LDR(T-rchild); ret

37、urn(0); （1） 从前面的三种遍历算法可以知道：如果将printf语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。对遍历的分析：后序遍历递归算法：LRD (BiTree T) if(T) LRD(T-lchild); LRD(T-rchild); printf(“%d”,T-data); return(0);（2） 二叉树遍历的时间效率和空间效率 时间效率:O(n) /每个结点只访问一次 空间效率:O(n) /栈占用的最大辅助空间递归遍历算法的应用举例1、统计二叉树中叶子结点的个数2、求二叉树的深度例1：编写递归算法，计算

38、二叉树中叶子结点的数目。 思路：这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将计数器count加1即可。下面这个算法是利用先序遍历实现的。void CountLeaf (BiTree T, int &count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); /if / CountLeaf例2：求二叉树的深度 思路：二叉树的深度应为其左、右子树深度的最大值加

39、1。由此，需先分别求得左、右子树的深度，只能采用后序遍历。算法中“访问结点”的操作为:求得左、右子树深度的最大值，然后加 1 。int Depth (BiTree T ) if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight)?depthLeft : depthRight); return depthval; 层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一

40、层中，则按从左到右的顺序对结点逐个访问。 -/+*abcdef遍历结果：- + / a * e f b c d1.在任何一棵二叉树中，如果结点a有左孩子b，右孩子c，则在结点的先序序列、中序序列、后序序列中， ( ) A.结点b一定在结点a的前面 B.结点a一定在结点c的前面 C.结点b一定在结点c的前面 D.结点a一定在结点b的前面2.设森林T中有3棵树，第一、二、三棵树的结点个数分别是n1、n2、n3，那么当把森林T转换成一棵二叉树后，根结点的右子树上有( ) 个结点。 A. n1+n2+n3 B. n2+n3 C. n1+n2 D. n1+n3练习例1：先序遍历的结果是：中序遍历的结果是

41、：后序遍历的结果是： A B CD ED B E A CD E B C A口诀：DLR先序遍历，即先根再左、右LDR中序遍历，即先左再根后右LRD后序遍历，即先左、右再根ABDEC层次遍历：ABCDE+*A*/EDCB先序遍历结果：+ * * / A B C D E前缀表示法（波兰式）中序遍历结果：A / B * C * D + E中缀表示法后序遍历结果：A B / C * D * E +后缀表示法（逆波兰式）例2：用二叉树表示算术表达式层次遍历结果：+*E*D/CAB例3 写出如图6.2所示的二叉树的前(先)序中序和后序遍历序列.解：前序为“根左右”，从左到右收集的前序序列为： 中序为“左根

42、右”，从左到右收集的中序序列为： 后序为“左右根”，从左到右收集的后序序列为： fdgibehjacfdbacegihjabcdefghijacbedhjigf例4一棵二叉树如图所示：写出对此树的先根、中跟、后跟序列。先根序列:ABDEFC中根序列:DEFBAC后根序列:FEDBCA7.6.2 二叉树的构造若已知一棵二叉树的先序（或中序，或后序，或层序）序列，能否惟一确定这棵二叉树呢？遍历的性质性质1、由一棵二叉树的先序序列和中序序列可惟一确定这棵二叉树性质2、由一棵二叉树的后序序列和中序序列可惟一确定这棵二叉树由遍历序列恢复二叉树例如，已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG

43、和DECBHGFA，试画出这棵二叉树。构造二叉树过程如下：BDCEFHGAFHGABDCE由遍历序列恢复二叉树7.6.2 二叉树的构造FHGABDCEFABECDGHFHGABCDEHGABCDEF由遍历序列恢复二叉树中序序列BDCEAFHG后序序列DECBHGFA7.6.2 二叉树的构造先序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 试构造二叉树。HBDFEKCGAEKCGABHDF7.6.2 二叉树的构造KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG先序序列 ABHFDECKG 7.6.2 二叉树的构造a b c d e f gc b d a e

44、 g f例如:aab bccddeeffggabcdefg先序序列中序序列例1 已知一棵二叉树的后序遍历序列为DGEBHFCA，中序遍历序列为DBEGAHCF，画出该二叉树，并写出二叉树的先序遍历序列。 先序遍历序列：ABDEGCHF先序序列为：中序序列为：例2：已知一棵二叉树的先序序列为CEDBA，中序序列为DEBAC，试构造该二叉树。 基本思想： 在先序序列中找根，在中序序列中分左右。DEBACEDABDEBCAECBABDA例3先序序列为：A B D E C F H G中序序列为：D B E A H F C G构造一棵二叉树。答案例4：已知一棵二叉树的后序序列为DABEC，中序序列为DE

45、BAC，试构造该二叉树。 基本思想： 在后序序列中找根，在中序序列中分左右。DEBA后序序列为：中序序列为：DABCEDEBCAECBABDA例5后序序列为：D E B H F G C A中序序列为：D B E A H F C G构造一棵二叉树。答案DEGFBCAH例6 设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： ABDFCEGH 中序遍历序列：BFDAGEHC（1）画出这棵二叉树。（2）将这棵二叉树转换成对应的树（或森林）ABFDCEHG例7 如果已知森林的前序序列和后序序列分别为ABCDEFIGJH和BDCAIFJGHE，请画出该森林。【解】由于森林的前序序列与其对应的二叉树前序

46、序列相同，而森林的后序序列与其对应的二叉树中序序列相同。因此，根据二叉树前序序列ABCDEFIGJH和中序序列BDCAIFJGHE可画出二叉树如下图所示。ABEDCGJIFH而由二叉树转化为森林的步骤得到对应的森林。ABDCEGJIFH所以， 空指针数目2n(n-1)=n+1个。证明：用二叉链表存储包含n个结点的二叉树，结点必有2n个链域。除根结点外，二叉树中每一个结点有且仅有一个双亲，意即每个结点地址占用了双亲的一个链域，n个结点地址共占用了n-1个指针域。也就是说，只会有n1个链域存放指针。讨论1：用二叉链表法（l_child, r_child）存储 包含n个结点的二叉树，结点的指针区域中

47、 会有多少个空指针？有n+1个！7.7 线索二叉树结论：用二叉链表存储包含n个结点的二叉树，结点的指针区域中会有n+1个空指针。讨论2：二叉树是非线性结构，如何定义其直接后继？ 对二叉树进行某种遍历之后，将得到一个线性 有序的序列。 例如对某二叉树的中序遍历结果是B D C E A F H G，意味着已将该树转为线性排列，显然其中结点具有唯一前驱和唯一后继。 讨论3：如何获得这种“直接前驱”或“直接后继”？这就是线索二叉树（Threaded Binary Tree）二叉树中容易找到结点的左右孩子信息，但该结点的直接前驱和直接后继只能在某种遍历过程中动态获得。先依遍历规则把每个结点对应的前驱和后

48、继线索预存起来，这叫做“线索化”。意义：从任一结点出发都能快速找到其前驱和后继，且不必借助堆栈。线索二叉树线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；加上线索的二叉链表称为线索链表线索二叉树：加上线索的二叉树称为线索二叉树。线索化过程就是在遍历过程中修改空指针的过程：将空的lchild改为结点的直接前驱；将空的rchild改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为“正常情况”）充分利用那n+1个空链域。规 定：1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱

49、(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索) 。datalchildrchild如何判断是孩子指针还是线索指针？如何区别？lchildLTagdataRTagrchild约定:当Tag域为0时,表示孩子情况;当Tag域为1时,表示线索情况.前驱(后继)左(右)孩子为区别两种不同情况，特增加两个标志域：问：增加了前驱和后继等线索有什么好处？能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整棵树。各1bit ltag lchild data child rtag0: lchild指向该结点的左孩子1: lchild指向该结点的前驱结

50、点0: rchild指向该结点的右孩子1: rchild指向该结点的后继结点ltag=rtag=结点结构如何进行二叉树的线索化呢？ 线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱和后继的信息只有在遍历时才能得到，因此线索化过程即为在遍历的过程中修改空指针的过程。线索二叉树线索二叉树的生成算法目的：在遍历二叉树的过程中修改空指针，添加前驱或后继的线索，使之成为线索二叉树。 为了记下遍历过程中访问结点的先后次序，需要设置两个指针： p指针当前结点之指针； pre指针当前结点的前趋结点指针。设计技巧：依某种顺序遍历二叉树，对每个结点p，判断其左指针是否为空，以及其前

51、驱结点的右指针是否为空。每次只修改前驱结点的右指针（后继）和本结点的左指针（前驱）。若p-lchildNULL,则 p-LTag=1; p-lchildpre; /p的前驱线索应存p结点的左边若pre-rchildNULL, 则 pre-RTag1; pre-rchild=p; /pre的后继线索应存pre结点的右边难点：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。以中序线索二叉树为例：当RTag=1时，直接后继指针就在其rchild域内；当RTag=0时，直接后继是遍历当前结点的右子树时访问的第一个结点，即右子树中最左下方的结点；请

52、注意中序遍历规则是LDR，先左再根再右3. 线索二叉树的遍历（无需堆栈）对于线索二叉树的遍历，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空为止。（因为建立线索时已遍历一次，相当于线性化了！）ABCGEIDHFroot悬空？ NIL悬空？ NIL解：对该二叉树中序遍历的结果为: H, D, I, B, E, A, F, C, G 所以添加线索应当按如下路径进行：为避免悬空态，应增设一个头结点例1：画出以下二叉树对应的中序线索二叉树。 线索二叉树的生成线索化00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为: H, D, I, B, E, A, F, C

53、, G对应的中序线索二叉树存储结构如图所示：root例如 对如下图所示的二叉树: 写出对它们进行先序中序和后序遍历时得到的结点序列; 画出它们的先序线索二叉树和后序线索二叉树。【解】对图进行先序中序和后序遍历时得到的结点序列分别如下:先序遍历的结点序列为：ABDFGHIEC中序遍历的结点序列为：FDHGIBEAC后序遍历的结点序列为：FHIGDEBCAABCGDEHIF二叉树的先序线索二叉树如下左图所示，后序线索二叉树如下右图所示。ABCGDEHIFNIL先序线索二叉树ABCGDEHIF后序线索二叉树NIL相关概念1.结点间的路径长度-从树中一个结点到另一个结点之间的分支数目7.8 哈夫曼树及

54、其应用2.叶子结点的权值-对叶子结点赋予的一个有意义的数值量。 3.结点带权的路径长度-从该结点到树根之间的路径长度与结点上权的乘积。23477.8 哈夫曼树及其应用4.二叉树的带权路径长度（weighted path length of tree）-二叉树中所有叶子结点的带权路径长度之和。WPL=nkkklw1第k个叶子的权值；从根结点到第k个叶子的路径长度ABCD2347WPL=2*2+3*2+4*2+7*2=327.8 哈夫曼树及其应用5.哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树,称为哈夫曼树（也称最优树） 。例：给定4个叶子结点，其权值分别为2，3，4，7，可

55、以构造出形状不同的多个二叉树。 WPL=32 WPL=41 WPL=302347234774237.8 哈夫曼树及其应用哈夫曼树的特点：1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。 2. 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点. 2347WPL=32 WPL=41 WPL=30234774237.8 哈夫曼树及其应用哈夫曼算法基本思想： 初始化：由给定的n个权值w1，w2，wn构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合FT1，T2，Tn； 选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树

56、，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和； 删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中； 重复、两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。 怎样构造一棵哈夫曼树呢？8W= 0.05， 0.29， 0.07， 0.08， 0.14， 0.23， 0.03， 0.1152971481523311835191578294258100建立哈夫曼树示例的演示创建完毕146/157.8 哈夫曼树及其应用 给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树,要求左子树根结点的权值小于右子树根结点的权值。课堂练习11529

57、7814233100011558290001118421900011100000001001011110111111010哈夫曼树及应用定理7.3 一棵有n个叶子结点的Huffman树有2n-1个结点。n1 = 0：因为每次两棵树合并。n = n0+n1+n2 = n0+n2 = 2n0-1。哈夫曼树的存储结构 用一个大小为2n-1的向量来存储哈夫曼树中的结点，其存储结构为： typedef struct /结点类型 int weight； /权值，不妨设权值均大于零 int lchild，rchild，parent； /左右孩子及双亲指针 HTNode，*HuffmanTree;Weight

58、 parent lchild rchild 1 2 3 4 5 6 7 8 9101112131415529781423311 0 1 2 3 4 5 6 7W529870000000000000000000000000000000000000000000001423311999178101034151111128191414121313151552942581002101161412130HC 0cd 0 1 2 3 4 5 6 7123456781000 start0001求哈夫曼编码过程的实例:HT数组1011101111110010000001void CreateHT(HTNode ht,int n0)/构造哈夫曼树int i,k,lnode,rnode;double min1,min2;for (i=0;i2*n0-1;i+)/所有节点的相关域置初值-1hti.parent=hti.lchild=