数据结构,第六章 二叉树,课件函试题

1、第六章 二叉树n6.1 二叉树的定义与性质n6.2 二叉树的基本操作与存储实现n6.3 二叉树的遍历n6.4 线索二叉树n6.5 树和森林n6.6 哈夫曼树（赫夫曼树）6.1.1 二叉树的基本概念1、定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 二叉树是有序的，将左右子树颠倒，就形成 一个不同的二叉树。二叉树具有5种基本形态，如下图：n6.1 树的定义与性质(a)空二叉树A(b)左右子树为空的树AB(c)右子树为空的二叉树AB(d) 左子树为空的二叉树ACB (e)包含左右子树的二叉树2、二叉树的相关

2、概念：l结点的度：结点拥有的子树的个数称为该结点的度。l叶结点:度为0的结点称为叶结点，或者称为终端结点。l分支结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶子节点外，其余的都是分支结点。l左孩子、右孩子、双亲、兄弟：树中一个结点的子树的根节点称为这个结点的孩子。在二叉树中，左子树的根称为左孩子，右子树的根称为右孩子。这个结点称为他孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。l路径、路径长度：如果一棵树的一串结点n1,n2,nk有如下关系：结点ni是ni+1的父结点(1i k)，就把n1,n2,nk称为一条由n1 nk的路径，这条路径的长度是k-1.l祖先、子孙

3、：在树中，如果有一条路径从结点M到结点N,那么M就称为N的祖先，而N就称为M的子孙。l结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1.l树的深度：树中所有结点的最大层数称为数的深度。l树的度：树中所有结点度的最大值称为该树的度。l满二叉树：满二叉树：在一棵二叉树中，如果所有分支结点都存在左在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称为满二叉树。一棵二叉树称为满二叉树。123456789 10 11 12 13 14 15l完全二叉树：深度为k的，有n个结点

4、的二叉树，对树中的结点按从上到下、从左到右的顺序进行编号，如果编号为i的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为满二叉树。abcdefghij完全二叉树的特点：完全二叉树的特点：(1)(1)叶子结点只能在层次最大的两层上出现。叶子结点只能在层次最大的两层上出现。(2)(2)对任一结点，若其右分支下的子孙的最大层次对任一结点，若其右分支下的子孙的最大层次 为为m m，则其左分支下的子孙上的最大层次必为，则其左分支下的子孙上的最大层次必为m+1m+1。6.1.2 二叉树的性质n性质1：一棵非空二叉树的第i层上至多有2i-1个结点(i=1)。采用归纳法证明此性质。 当i=

5、1时，只有一个根结点，2i-1=20 =1,命题成立。 现在假定对所有的j，1=j=1)。 分析：深度为k的二叉树的最大的结点为二叉树中每层上的最大结点数之和。 由性质1得到每层i上的最大结点数为2i-1，那么 所有结点数为 = 2k 1k11 - i2in性质3：对任何一棵二叉树，如果叶子结点数为n0，度为2的结点数为n2，则n0n21。 设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点的度均小于或等于2，所以其结点总数：Nn0n1n2 （61) 再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：NB1。由于这些分支都是由度

6、为1和2的结点发出的，所以有： Bn1+2*n2即得，NB1n12*n21 （62)由式（61）和（62）得到： n0+n1+n2=n1+2*n2+1 n0n21n性质4：具有n个结点的完全二叉树的深度为 1 符号 x 表示不大于x的最大整数。 证明：假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到： 2k-11n2k-1 或 2k-1n2k 取对数得到：k1log2nk 因为k是整数。所以有： k 1。logn2 logn2n性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第 +1层，每层从左到右),则对任一结点i（1=i1，则其双亲是结点 i/2 。 （2）如

7、果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。 （3）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。logn2例1：二叉树的第k层的结点数最多为( ). A2k-1 B.2K+1 C.2K-1 D. 2k-1例2：一棵高度为5的二叉树中最少含有_ 个结点，最多含有_个结点；例3：在一棵非空二叉树中,度为2的结点个数为5,度为0的结点个数 ( ) A4 B5 C6 D7例4：9根据二叉树的定义可知二叉树共有（ ）种不同的形态。(A) 4 (B) 5 (C) 6 (D) 7D531性质性质2性质性质1性质性质3CBn6.2 二叉树的基本操作与存储实现6.2.1二叉

8、树的存储1、顺序存储结构、顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。一般它是用一组连续的存储单元存储二叉树的数据元素。一般是按照二叉树结点从上至下，从左到右的顺序存储。是按照二叉树结点从上至下，从左到右的顺序存储。ABCDEFGHIJABD EFG HCIJ01345 67892完全二叉树的顺序存储 对于一般的二叉树，如果仍按从上到下和从左到右的顺序将树中的结点顺序存储在一维数组中，需添加一些不存在的空节点，使它变成一个完全二叉树。ABCEFGJAB D E C F一般二叉树的顺序存储 GABCDEFG 结论：显然这种需增加许多空结点才能将一棵二叉树改造成一棵完全二叉树的存储

9、，会造成空间的大量浪费，不宜采用顺序存储结构，满二叉树和完全二叉树比较适合顺序存储。2、链式存储结构 所谓二叉链表存储结构，是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常有下面两种形式：（1）二叉链表存储 链中每个结点由3个域组成，除了数据域外，还有两个指针域，分别用来给出结点的左孩子和右孩子。结点存储结构：lchild data rchild 存储二叉树经常用二叉链表法，如下图：ABC D E F GH lchildDatarchild头指针bt不带头结点的二叉链表 二叉链表也可以带头结点的方式存放，如下图：ABC D E F GH lchildDatarchild头结点指针b

10、t带头结点的二叉链表 二叉链表存储表示为：typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree 结点结构：lchild data rchild（2）三叉链表存储 链中每个结点由4个域组成，结点存储结构： 其中，data、lchild以及rchild这三个域和二叉链表结构相同；parent域向该结点双亲结点的指针。这种结构既便于查找孩子结点，又便于查找双亲结点；但是相对于二叉链表，三叉链表增加了空间开销。lchild data rch

11、ildparent 三叉链表存储 lchild data rchildparentADEBCF typedef struct TriTNode / 结点结构结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;parent lchild data rchild结点结构结点结构: :三叉链表的存储表示可描述为: :6.2.2二叉树的基本操作及实现1、二叉树的基本操作 InitBiTree(bt); /建立一棵空二叉树建立一棵

12、空二叉树 Create(x,lbt,rbt); /生成一棵以生成一棵以x为根结点的数据域为根结点的数据域信息，以二叉树信息，以二叉树lbt和和rbt为左子树和右子树的二叉为左子树和右子树的二叉树。树。 InsertLChild(bt, x, parent); /将数据信息为将数据信息为x的结的结点插入到二叉树点插入到二叉树bt中作为结点中作为结点parent的左孩子结点。的左孩子结点。如果原来结点如果原来结点parent原来有左孩子结点，则将结点原来有左孩子结点，则将结点parent原来的左孩子结点作为结点原来的左孩子结点作为结点x的左孩子结点。的左孩子结点。DeleteLChild(bt,

13、parent); /在结点在结点bt中删除结点中删除结点parent的左子树。的左子树。 Search(bt，x); /在二叉树在二叉树bt中查找数据元素中查找数据元素x。 Traverse(bt); /按某种方式遍历二叉树按某种方式遍历二叉树bt的全部结点。的全部结点。2、算法实现、算法实现 int InitBiTree(BiTNode bt); /建立一棵空二叉树建立一棵空二叉树 bt = new BiNode; if(!bt) return 0; /没有存储空间返回0 bt-lchild=NULL; bt-rchild=NULL; return 1; /返回成功代码1main() BiT

14、ree t; Initiate(&t); 二叉树的遍历是按照某种顺序访问二叉树的每个结点，是每个结点被访问一次且仅被访问一次。 二叉树的三个基本组成单元是：根结点、左子树和右子树。 假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为： DLR先（根）序遍历， LDR中（根）序遍历， LRD后（根）序遍历。n6.3二叉树的遍历1、先序遍历二叉树的操作定义为：若二叉树为空，则遍历结束；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。例如图中所示的二叉

15、树表达式若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为： -+a*b-cd/ef*a/b-dcfe2、中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。例如图中所示的二叉树表达式按中序遍历,其中序序列为： a+b*c-d-e/f*a/b-dcfe3、后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。例如图中所示的二叉树表达式按后序遍历,其后序序列为： abcd-*+ef/-*a/b-dcfe4、层次遍历二叉树的操作定义为： 从二叉树的第一

16、层开始，从上至下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。例如图中所示的二叉树表达式按层次遍历,其层次序列为： -+/a*efb-cd*a/b-dcfeABCDEFGHK例如:先序先序序列: A B C D E F G H K中序中序序列: B D C A H G K F E后序后序序列: D C B H K G F E A 当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能在任一序列中找到结点的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加两个标志域。 若该结点的左子树不空，若该结点的左子树不空，则Lchild域的指针指向其左子

17、树，且左标志域的值为“指针 Link”或0；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索 Thread”或1 。n6.4线索二叉树lchildLTagdataRTagrchild 若该结点的右子树不空，若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为 “指针 Link”或0；否则，rchild域的指针指向其“后继”，且右标志的值为“线索 Thread”或1。即: 0 lchild 域指示结点的左孩子 1 lchild 域指示结点的前驱 0 rchild 域指示结点的右孩子 1 rchild 域指示结点的后继 以这种结构构成的二叉链表作为二叉树的存储结

18、构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。n6.4线索二叉树ltag =rtag= n6.4线索二叉树ABDCGFE(a)先序线索二叉树GABDCFE(b)中序线索二叉树ABDCGFE(c)后序线索二叉树例如：例如：0100A01B10D11G00C11E11Fbt中序线索二叉树存储n6.5 树和森林6.5.1 树的定义及相关术语 树是n(n0)个有限数据水元素的集合。当n=0时称这棵树为空树。在一棵非空树T中 : 有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。 若n1,除根结点以外的其余数据元素被分成m(m0) 个互不相交的集合T1,

19、T2,Tm，其中每一个集合Ti(1i m)本身又是一棵树。树T1,T2,Tm称为这个根节点的子树。 树的定义可以描述为二元组的形式 T=(D,R) 其中，D为树T中结点的集合，R为树中结点之间关系的集合。n6.5 树和森林 6.5.1 树的定义 当树为空树时，D=；当树T不为空树时，有 D=root DF 其中，D为树T中结点的集合，R为树中结点之间关系的集合。DF可由下式表示 DF= D1 D2 Dm且且Di Dj=(ij,1i m, 1j m)当树T中结点个数n 1时，时，R=；当树T中结点个数n1时，有R=,1,2,m,其中，root为树T的根结点root的子树的Ti的根结点。 如图是一

20、棵有9个结点的树，即T=A,B,C,H,I,结点A为树T的根结点，除根结点A的其余结点分为两个不相交的集合T1=B,D,E,F,H,I和T2=C，G，构成了结点A的两棵子树，T1和T2本身也分别是一棵树。例如，子树T1的根结点为B，其余结点又分为3个不相交的集合：T11=D, T12=F,H,I和T13=E。 T11, , T12, T13构成了子树T1的根结点B的三棵子树。如此继续分为更小的树。ABCDFGHIE 从树的定义和上图的示例可以看出，树具有下面两个特点： 树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。树中所有结点可以有零个或者多个后继结点。由此可知下图均不是

21、树结构：ABDECGFABDECGF 6.5.2 相关术语 (1)有序树和无序树，如果一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。 (2)森林，零棵或有限棵不相交的树的集合称为森林。 任何一棵树，删去根结点就变成了森林。 6.5.3 树的表示 1、直观表示法 ABCDEF G H I JMKL2、嵌套集合表示法 所谓嵌套集合是指一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个。用嵌套集合的形式表示树，就是将根节点视为一个大的集合，其若干棵树、子树构成这个大集合中若干个互不相交的子集，如此嵌套

22、下去，即构成了一棵树的嵌套集合表示。 ABKELFDHMJICG嵌套集合表示法嵌套集合表示法ABCDEF G H I JMKL3、广义表表示法 将根作为由子树森林组成的表的名字写在表的左边，这样依次将树表示出来。ABCDEF G H I JMKL（A(B(E,F(K,L),C(G),D(H,I,J(M)广义表表示法广义表表示法4、凹入表示法 每个结点对应一个矩形，所有结点的矩形都是右对齐，根结点用最长的矩形表示，同一层的结点的矩形长度相同，层次越高，矩形长度越短。 ABCDEF G H I JMKLABCDEKLFGHIJM凹入表示法凹入表示法6.5.4树的存储结构 树的存储有多种方式，既可以

23、采用顺序存储结构，也可以采用链式存储结构，存储结构不但要求存储结点本身的数据信息，还要能唯一反应树中各节点之间的逻辑关系。1、双亲表示法 用一组连续的存储空间(一维数组)存储树中各个结 点，数组中的一个元素表示树中一个结点，数组元素 为结构体类型，其中包括结点本身的信息和结点的双 亲结点在数组中的序号。双亲表示法双亲表示法:序号dataABCDEFGHIparent-100111244ABCDEFGHI一棵树结构data parent结点结构：结点结构：#define MAX_TREE_SIZE 100 typedef struct PTNode Elem data; int parent;

24、/ 双亲位置域 PTNode; 树结构树结构:typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;存储表示如下：存储表示如下：2、孩子表示法(1)多重链表法 每个结点包括一个结点信息域和多个指针域，每 个指针域指向该结点的一个孩子结点，通过各个指针 域值反应出树中各节点之间的逻辑关系。结点的指针域的设置有两种方法： 每个结点指针域的个数等于该结点的度数。 每个结点指针域的个数等于树的度。每个节点指针域的个数等于该结点的度数。ABCDEABCDEFGHI一棵树结构每个节点指针域的个数等于树的度数。AF (

25、2)孩子链表表示法由一个与结点数一样大小的一维数组存放结点，数组的每个元素有两个域组成，一个域用来存放结点信息，另一个域用来存放指针，这个指针指向由该结点孩子组成的单链表的首地址。 序号 data firstchildABCDEFGHI12345678typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子结点结构孩子结点结构: :孩子链表存储表示孩子链表存储表示描述为描述为: :child nextdata firstchild typedef struct Elem data; ChildPtr firstchil

26、d; / 孩子链的头指针 CTBox;双亲结点结：双亲结点结： 3、双亲孩子表示法是将双亲表示法和孩子链表法相结合的结果。孩子结点组成单链表，同时用一维数组顺序存储树中的各结点，数组元素包括结点本身信息和结点孩子结点链表头指针和双亲结点在数组中的序号。 序号datafirstchildABCDEFGHI12345678parent-100111244 3、孩子兄弟表示法在树中每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。 AFtypedef struct CSNode Elem data; struct CSNode *firstchild, *next

27、sibling; CSNode, *CSTree;结点存储表示结点存储表示描述为描述为: :结点结构结点结构: : firstchild data nextsibling6.5.5树、森林与二叉树的转换 1、树转换为二叉树 对于一棵无序树，树中结点的各孩子的次序是无关紧要的，而二叉树终结点的左、右孩子结点是有区别的。为了避免发生混淆，约定树的每一个孩子结点按从左到右的顺序编号。如下图，根结点A有B、C、D三个孩子，可以认为结点B为A的第一个孩子结点，结点C为A的第二个孩子结点，结点D为A的第三个孩子结点。ABDCEFG 将一棵树转换为二叉树的方法如下： (1)树中所有相邻兄弟之间加一条连线 (

28、2)对树中每个结点，只保留它与第一个孩子结点之间的连线。 (3)以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。ABDCEFGABDCEFGABDCEFG 由转换可知，在二叉树中，左分支上的各由转换可知，在二叉树中，左分支上的各节点在原来的树中是父子关子，而右分支上的节点在原来的树中是父子关子，而右分支上的各结点在原来的树中是兄弟关系。由于树的根各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空。的右孩子必为空。2、森林转换为二叉树方法描述为： F = ( T1, T2, , Tm )是森林

29、，则可按如下规则转换成一棵二叉树B = (root，LB, RB)。l若 F = ，m=0,则 B = ；l若F ，B的根root即为森林中第一棵树的根ROOT( T1 ) ； B的左子树LB是从T1中根结点的子树森林F1=T11, T12, , T1m 转换成的二叉树；其右子树RB是从森林F= T1, T2, , Tm 转换而成的二叉树。 将森林转换为二叉树的方法如下： (1)将森林中的每棵树转换成相应的二叉树 (2)第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来以后，此时所得到的二叉树就是森林转换得到的二叉树。ABCDFE

30、JGHIKABCDFEJGHIKABCDFEJGHIK3、由二叉树转换为森林方法描述为：如果B=(root,LB,RB)是一棵二叉树，则按如下规则转换成森林F= ( T1, T2, , Tm )l若 B = B = ， 则 F = F = ；l若 B ，则森林中的第一棵树T1的根ROOT(TROOT(T1 1) )即即是B的根root；T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T T1 1外其余树组成的森林F= T1, T2, , Tm 是由B的右子树RB转换而成的森林。具体方法为：（1）结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子都与该节点的双亲结点用线连

31、起来。（2）删去原二叉树中所有的双亲结点与右孩子节点的连线。（3）整理（1）、（2）两步所得到的树或森林，使之结构层次分明。由二叉树转换为森林由二叉树转换为森林的转换过程：ABCDFEGHIABCDFEGHI(a)一棵二叉树(b)加连线ABCDFEGHI(c)去掉与右孩子的连线FEGHIABC D(d)还原后的森林树的遍历可有三条搜索路径树的遍历可有三条搜索路径: :按层次遍历按层次遍历: :先根先根( (次序次序) )遍历遍历: :后根后根( (次序次序) )遍历遍历: : 若树不空，则先访问根结点，然后依次先根若树不空，则先访问根结点，然后依次先根遍历各棵子树。遍历各棵子树。 若树不空，则

32、先依次后根遍历各棵子树，然若树不空，则先依次后根遍历各棵子树，然后访问根结点。后访问根结点。 若树不空，则自上而下自左至右访问树若树不空，则自上而下自左至右访问树中每个结点。中每个结点。6.5.6树和森林的遍历树和森林的遍历1 1、树的遍历、树的遍历先根遍历时顶点的访问次序：先根遍历时顶点的访问次序：A B C E F G D后根遍历时顶点的访问次序：后根遍历时顶点的访问次序：B E G F C D A层次遍历时顶点的访问次序：层次遍历时顶点的访问次序：A B C D E F G ABCDEFG B C DE F G H I J K1 1森林中第一棵树的根森林中第一棵树的根结点；结点；2 2森

33、林中第一棵树的子森林中第一棵树的子树森林；树森林；3 3森林中其它树构成的森森林中其它树构成的森林。林。森林由三部分构成：森林由三部分构成：2 2、森林的遍历、森林的遍历 若森林不空，则若森林不空，则l访问访问森林中第一棵树的根结点；l先序遍历先序遍历森林中第一棵树的子树森林；l先序遍历先序遍历森林中(除第一棵树之外)其余树构成的森林。(1)(1)先序遍历森林先序遍历森林即：依次从左至右依次从左至右对森林中的每一棵树树进行先先根遍历根遍历。(2)(2)中序遍历中序遍历若森林不空，则若森林不空，则l中序遍历中序遍历森林中第一棵树的子树森林；l访问访问森林中第一棵树的根结点；l中序遍历中序遍历森林

34、中(除第一棵树之外)其 余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行后根后根遍历遍历。 B C DE F G H I J K例如例如： 先序遍历时顶点的访问次序：先序遍历时顶点的访问次序：B E F C D G H I J K后序遍历时顶点的访问次序：后序遍历时顶点的访问次序：E F B C I J K H G Dn6.6哈夫曼树(霍夫曼树) 6.6.1 哈夫曼树的基本概念 哈夫曼树，也称最优二叉树，是指对于一组带有确定权值的叶子结点，构造的具有最小带权路径长度的二叉树。l路径长度路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称

35、做路径长度。l树的路径长度树的路径长度：是从树根到每一结点的路径长度之和。l结点的带权路径长度结点的带权路径长度：从根结点到该结点的路径长度与结点上权的乘积。l树的带权路径长度树的带权路径长度：根结点到各个叶子结点的路径长度与相应结点权值的乘积之和 WPL(T) = wklk (对所有叶子结点) 在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值带权路径长度取最小值的树，称为“最优树最优树”或者“哈夫曼树哈夫曼树”。(a)WPL(T)= 72+52+22+42=36(b)WPL(T)= 73+53+42+21=46(c)WPL(T)= 71+52+23+43

36、=35 如何构建最优树？树的带全路径长度：树的带全路径长度： 哈夫曼树依据这一特点提出了这种方法，基本思想是：n根据给定的 n 个权值 w1, w2, , wn，构造 n 棵只有一个叶子结点的二叉树，从而得到一个二叉树的集合F = T1, T2, , Tn。n在 F 中选取其根结点的权值为最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；n从F中删去这两棵树，同时将新建立的二叉树加入到集合F中；n重复(2)和(3)两步，直至 F 中只含一棵树为止。这棵树便是哈夫曼树。9例如: 已知权值 W= 5, 6, 2, 9, 7 56275

37、2769779613527 7575796713527 757 720952720671329注意：注意： 初始森林中的初始森林中的n n棵二叉树，每棵树有一个孤立的棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子结点，它们既是根，又是叶子 n n个叶子的哈夫曼树要经过个叶子的哈夫曼树要经过n-1n-1次合并，产生次合并，产生n-1n-1个新结点。最终求得的哈夫曼树中共有个新结点。最终求得的哈夫曼树中共有2n-12n-1个结个结点。点。 哈夫曼树是严格的二叉树，没有度数为哈夫曼树是严格的二叉树，没有度数为1 1的分支的分支结点。结点。6.6.2 6.6.2 哈夫曼编码哈夫曼编码1 1、不

38、等长编码、不等长编码 这种编码方式的特点这种编码方式的特点: :每个字符的编码每个字符的编码长度相同长度相同。 设字符集只含有设字符集只含有4 4个字符个字符A A，B B，C C，D D，用两位二进，用两位二进制表示的编码分别为制表示的编码分别为0000，0101，1010，1111。若现在电文为：。若现在电文为：ABACCDAABACCDA，则应发送二进制序列：，则应发送二进制序列：0001001010110000010010101100，总长度为总长度为1414位。当接收方接收到这段电文后，将按两位位。当接收方接收到这段电文后，将按两位一段进行译码。一段进行译码。这种编码的特点这种编码的

39、特点: : 译码简单且具有唯一性，但编码长度并不是最短的。译码简单且具有唯一性，但编码长度并不是最短的。2. 2. 不等长编码不等长编码 在传送电文时，为了使其二进制位数尽可能地少，在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较可以将每个字符的编码设计为不等长的，使用频度较高高的字符分配一个相对比较的字符分配一个相对比较短短的编码，使用频度较的编码，使用频度较低低的字符分配一个比较的字符分配一个比较长长的编码。的编码。例如，可以为例如，可以为A A，B B，C C，D D四个字符分别分配四个字符分别分配0 0，0000，1 1，0101，并可将上述电

40、文用二进制序列：，并可将上述电文用二进制序列：000011010000011010发送，发送，其长度只有其长度只有9 9个二进制位。个二进制位。 但随之带来了一个问题，接收方接到这段电文后但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面无法进行译码，因为无法断定前面4 4个个0 0是是4 4个个A A，1 1个个B B、2 2个个A A，还是，还是2 2个个B B，即译码不唯一，因此这种编码，即译码不唯一，因此这种编码方法不可使用。方法不可使用。3 3、哈夫曼编码、哈夫曼编码 利用哈夫曼树可以构造一种不等长的二进制编利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所

41、得的码，并且构造所得的哈夫曼编码哈夫曼编码是一种是一种最优前缀编码最优前缀编码，即：使所传即：使所传电文的总长度最短电文的总长度最短。哈夫曼编码的构造方法：哈夫曼编码的构造方法：（1 1）利用字符集中每个字符的使用频率作为权值构造）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；一个哈夫曼树；（2 2）从根结点开始，为到每个叶子结点路径上的左分）从根结点开始，为到每个叶子结点路径上的左分支赋予支赋予0 0，右分支赋予，右分支赋予1 1，并从根到叶子方向形成该叶，并从根到叶子方向形成该叶子结点的编码。子结点的编码。1152978142331000115582900011184219000

42、11100010011001111110111111010Weight parent lchild rchild 1 2 3 4 5 6 7 8 9101112131415529870000000000000000000000000000000000000000000001423311999178101034151111128191414121313151552942581002101161412130HTHT数组数组哈夫曼编码存储结构哈夫曼编码存储结构: :HCHC12345678001111111111111110000000015, 29, 7, 8, 14, 23, 3, 111. 熟

43、练掌握二叉树的结构特性二叉树的结构特性，了解相应的证明方法。2. 熟悉二叉树的各种存储结构存储结构的特点及适用范围。3. 遍历二叉树遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法递归算法，灵活运用遍灵活运用遍历算法历算法实现二叉树的其它操作。层次遍历层次遍历是按另一种搜索策略进行的遍历。4. 理解二叉树线索化的实质线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程线索化过程是基于基于对二叉树进行遍历遍历，为相应的遍

44、历提供为相应的遍历提供了方便方便。5. 熟悉树的树的各种存储结构存储结构及其特点，掌握树和森林与二叉树的转换树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握掌握 1 至 2 种建立建立二叉树和树的存储结构的方法存储结构的方法。6. 学会编写实现树的各种操作实现树的各种操作的算法。7. 了解最优树的特性最优树的特性，掌握建立最优树建立最优树和哈夫曼编码和哈夫曼编码的方法。n1 1）在一棵二叉树上第）在一棵二叉树上第4 4层的结点数最多是层的结点数最多是_。 A.4 B.8 C.32 D.12A.4 B.8 C.32 D.12n2) 2) 在深度为在深度为5 5的满二叉树中，叶子结点的个数为的满二叉树中，叶子结点的个数为_。 A.32 B.31 C.16 D.15A.32 B.31 C.16 D.15n3) 3) 在深度为在深度为5 5的二叉树中，至多有的二叉树中，至多有_个结点。个结点。n A.32 B.31 C.16 D.15A.32 B.31 C.16 D.15n4 4）在具有）在具有10 10 个结点的树中，其边的树目为个结点的