《数据结构第六章》由会员分享，可在线阅读，更多相关《数据结构第六章（54页珍藏版）》请在文档大全上搜索。
1、第六章 二叉树教学内容：教学内容： 6.1 定义与性质定义与性质 6.2 存储实现基本操作的实现存储实现基本操作的实现 6.3 二叉树的遍历二叉树的遍历 6.4 线索二叉树线索二叉树 6.5 二叉树的应用二叉树的应用 教学目的：教学目的： 深刻理解二叉树的定义、性质及其存储深刻理解二叉树的定义、性质及其存储方法；方法； 熟练掌握二叉树的二叉链表存储方式、熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义；结点结构和类型定义； 理解并掌握二叉树的三种遍历算法；理解并掌握二叉树的三种遍历算法； 掌握二叉树的线索化方法；掌握二叉树的线索化方法； 灵活运用二叉树的遍历方法解决相关的灵活运用二叉树的遍
2、历方法解决相关的应用问题；应用问题； 教学重点：教学重点：二叉树的定义、逻辑特点及性质，在二叉树二叉树的定义、逻辑特点及性质，在二叉树上定义的基本运算；上定义的基本运算； 二叉树的链式存储结构及其类型说明，二叉二叉树的链式存储结构及其类型说明，二叉树的顺序存储结构及其树的顺序存储结构及其 类型说明；类型说明； 二叉树链式存储结构的组织方式；二叉树链式存储结构的组织方式； 二叉树的三种遍历方法及其算法；二叉树的三种遍历方法及其算法； 以遍历为基础在二叉树上实现的几种运算；以遍历为基础在二叉树上实现的几种运算； 哈夫曼树和哈夫曼算法；哈夫曼树和哈夫曼算法；教学难点：教学难点：二叉树的递归定义；二叉
3、树的递归定义； 二叉树链式存储结构的组织方式；二叉树链式存储结构的组织方式； 三种遍历的主要区别；三种遍历的主要区别； 二叉树上的复杂运算；二叉树上的复杂运算； 哈夫曼算法及其应用；哈夫曼算法及其应用；学时安排：学时安排：10学时学时6.1 6.1 树的定义和基本术语树的定义和基本术语定义：定义：树树( (Tree)Tree)是是n(n=0)n(n=0)个结点的有限集个结点的有限集T T，T T为空时称为空树，否则它满足如下两个条件：为空时称为空树，否则它满足如下两个条件：（1 1）有且仅有一个特定的称为根）有且仅有一个特定的称为根( (Root)Root)的结点；的结点；（2 2）其余的结点
4、可分为）其余的结点可分为m(m=0)m(m=0)个互不相交的子集个互不相交的子集T T1 1,T,T2 2,T,T3 3T Tm m，其中每个子集又是一棵树，并称其其中每个子集又是一棵树，并称其为子树为子树( (Subtree)Subtree)。基本术语基本术语结点结点: :数据元素数据元素 + + 若干指向子树的分支若干指向子树的分支结点的度结点的度: :分支的个数分支的个数树的度树的度: :树中所有结点的度的最大值树中所有结点的度的最大值叶子叶子结点（结点（终端结点终端结点）: :度为零的结点度为零的结点分支分支结点结点: :度大于零的结点度大于零的结点从根到结点的从根到结点的路径路径：孩
5、子孩子结点、结点、双亲双亲结点、结点、兄弟兄弟结点、结点、祖先祖先结点、结点、子孙子孙结点结点结点的层次结点的层次: :假设根结点的层次为假设根结点的层次为1,1, 第第l层的结点的子树根结点的层次为层的结点的子树根结点的层次为l+1树的深度树的深度：树中叶子结点所在的最大层次：树中叶子结点所在的最大层次森林森林：是：是m（m0）棵互不相交的树的集合棵互不相交的树的集合任何一棵非空树是一个二元组任何一棵非空树是一个二元组Tree = （root，F）其中：其中： root被称为根结点，被称为根结点，F被称为子树森林被称为子树森林课堂练习：课堂练习：1、假设在树中，结点、假设在树中，结点x是结点
6、是结点y的双亲时，用的双亲时，用（x,y）来表示边。已知一棵树边的集合为：来表示边。已知一棵树边的集合为：（i,m）,(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用树形表示法画出此树，并回答下列问题：用树形表示法画出此树，并回答下列问题：1) 哪个是根结点？哪个是根结点？a2) 哪些是叶结点？哪些是叶结点？d,m,n,f,j,k,l3) 哪个是哪个是g 的双亲？的双亲？c4) 哪些是哪些是g的祖先？的祖先？a,c5) 哪些是哪些是g 的孩子？的孩子？j,k6) 哪些是哪些是e 的子孙？的子孙？m,
7、n,i7) 哪些是哪些是e的兄弟？的兄弟？d哪些是哪些是f 的兄弟？的兄弟？g,h8) 结点结点b和和h的层次各是多少？的层次各是多少？2,39) 树的深度是多少？树的深度是多少？510)以结点以结点e为根的子树的深度是多少？为根的子树的深度是多少？311)树的度数是多少？树的度数是多少？36.2 6.2 二二 叉叉 树树二叉树在树结构的应用中起着非常重要的作用，二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性存
8、储结构及其运算中存在的复杂性。6.2.1 6.2.1 二叉树的定义二叉树的定义二叉树是由二叉树是由n(n=0)n(n=0)个结点的有限集合构成，此集合或个结点的有限集合构成，此集合或者为空集，者为空集，或是由一个根结点加上两棵分别称为或是由一个根结点加上两棵分别称为左子左子树树和和右子树右子树的、的、互不相交互不相交的二叉树组成。的二叉树组成。二叉树不是树的特殊情况，它们是两个概念。有关数二叉树不是树的特殊情况，它们是两个概念。有关数的术语也都适用于二叉树。的术语也都适用于二叉树。特点：特点：每个结点至多只有二棵子树每个结点至多只有二棵子树子树有左右之分，次序不能任意颠倒子树有左右之分，次序不
9、能任意颠倒 二叉树的主要基本操作二叉树的主要基本操作：查找查找： Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();插入：插入： I
10、nitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);删除： ClearBiTree(&T); DestroyBiTree(&T); DeleteChild(T, p, LR); 二叉树的五种基本形态二叉树的五种基本形态：6.2.2 6.2.2 二叉树的性质二叉树的性质二叉树具有下列重要性质：二叉树具有下列重要性质：性质性质1 1 在二叉树的第在二叉树的第 i 层上至多有层上至多有2i-1 个结点。个结点。 (i1)性质性质 2 2 ： 深度为深度为 k 的二叉树上
11、至多含的二叉树上至多含 2k-1 个结点个结点（k1）。）。性质性质 3 3 ： 对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n0 个叶子结个叶子结点、点、n2 个度为个度为 2 的结点，则必存在关系式：的结点，则必存在关系式：n0 = n2+1。度：拥有结点的个数度：拥有结点的个数两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号为编号为 1 至至 n 的结点的结点一一对应。右结点缺123456789 10 11 12 13 14 15abcdefghij性质性质 4 4：具有
12、 n 个结点的完全二叉树的深度深度为 log2n +1 。深度-层性质性质 5 5：若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉 树 中 任 意 一 个 编 号 为 i 的 结 点 ：(1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲双亲结点；(2) 若 2in，则该结点无左孩子，否则，编号为 2 i 的 结 点 为 其 左 孩 子左 孩 子 结 点 ；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子右孩子结点。习题：习题：一个满二叉树有一个满二叉树有n 个结点，其中个结点，其
13、中m 个是叶结个是叶结点，树的深度是点，树的深度是 h，则表达式正确的是：则表达式正确的是： A、n = h+m B、h+m =2n C、 m= h-1 D、n=2 h -1一棵完全二叉树上有一棵完全二叉树上有1001个结点，其中叶子个结点，其中叶子结点的个数是结点的个数是_ a. 250 b. 501c. 254 d. 5056.2.3 6.2.3 二叉树的存储结构二叉树的存储结构一.顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在
14、这个序列中的相互位置能反映出结点之序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法间的逻辑关系，用编号的方法 #define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点 SqBiTree bt;从树根起，自上层至下层，每层自左至右的给所有结点从树根起，自上层至下层，每层自左至右的给所有结点编号，完全二叉树上编号为编号，完全二叉树上编号为i i的结点元素存储在如上的结点元素存储在如上定义的一维数组中下标为定义的一维数组中下标为i-1i-1的分量中。的分
15、量中。abcdefghijkl 编号：编号： 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树完全二叉树abcdefghijkl 存储单元：存储单元： 0 1 2 3 4 5 6 7 8 9 10 11 ABCDEFG 表示该处没有元素表示该处没有元素存在仅仅为了好理解存在仅仅为了好理解ABCDEFG一般二叉树一般二叉树 最坏的情况：最坏的情况：是右单支树，一棵深度为k的右单支树，只有k个结点，却需分配2k1个存储单元。缺点：缺点：是有可能对存储空间造成极大的浪费，是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为在最坏的情况下，一个深度为H H且只有且只有H H个结个
16、结点的右单支树确需要点的右单支树确需要2 2h h-1-1个结点存储空间。因个结点存储空间。因此仅适用于完全二叉树，此仅适用于完全二叉树，而且，若经常需要插入与删除树中结点时，而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！顺序存储方式不是很好！二、链式存储结构（重要）设计不同的结点结构可以构成不同形式的链式存储结构：设计不同的结点结构可以构成不同形式的链式存储结构：1 1、二叉链、二叉链表表链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为：ADEBCF root结点结构结点结构:lchild da
17、ta rchild 下图下图( (a)a)给出一棵二叉树的二叉链表示。二叉给出一棵二叉树的二叉链表示。二叉链表也可以带头结点的方式存放，如图链表也可以带头结点的方式存放，如图( (b)b)所示所示。C 语言的类型描述如下语言的类型描述如下: :typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;（2 2）三叉链表存储（）三叉链表存储（不要求不要求） 每个结点由四个域组成，具体结构为：每个结点由四个域组成，具体结构为：其中，其中，d
18、atadata、lchildlchild以及以及rchildrchild三个域的意义同二三个域的意义同二叉链表结构；叉链表结构；parentparent域为指向该结点双亲结点的指域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。，它增加了空间开销。 下图给出一棵二叉树的三叉链表示。 6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.3.1遍历二叉树一、问题的提出一、问题的提出顺着某一条搜索路径巡访巡访二叉树中的
19、结点，使得每个结点均被访问一次均被访问一次，而且仅被访问一次。仅被访问一次。 “访问访问”的含义可以很广，如：输出结点的信息等。 “遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构， 每个每个结点有两个后继结点有两个后继，则存在如何遍历存在如何遍历即按什么样的搜搜索路径索路径遍历的问题。假如以假如以L L、D D、R R分别表示遍历左子树、遍历根结点和分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有遍历右子树，遍历整个二叉树则有DLRDLR、LDRLDR、LRDLRD、DRLDRL、RDLRDL
20、、RLDRLD六种遍历方案。若规定先左后右，则六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：只有前三种情况，分别规定为： DLRDLR先（根）序遍历， LDRLDR中（根）序遍历， LRDLRD后（根）序遍历。由二叉树的递归定义，由二叉树的递归定义，二叉树的三个基本组成二叉树的三个基本组成单元是：根结点、左子单元是：根结点、左子树和右子树。树和右子树。bca(根结点)(右子树)(左子树)1、先序遍历二叉树先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则（1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树；）先序遍历左子树；（3 3）先序
21、遍历右子树。）先序遍历右子树。2、中序遍历二叉树中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则（1 1）中序遍历左子树；）中序遍历左子树；（2 2）访问根结点；）访问根结点；（3 3）中序遍历右子树。）中序遍历右子树。3、后序遍历二叉树后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则（1 1）后序遍历左子树；）后序遍历左子树；（2 2）后序遍历右子树；）后序遍历右子树；（3 3）访问根结点。）访问根结点。先根序列是：先根序列是： A B D C E G F H I ；中根序列是：中根序列是： D B A E G C H
22、F I 后根序列是：后根序列是： D B G E H I F C A ；可定义前驱及后继结点：可定义前驱及后继结点：如：二叉树中的结点如：二叉树中的结点C，它的先根前驱是它的先根前驱是D，先根后继是先根后继是E，中根前驱是中根前驱是G，对称序后继是对称序后继是H 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树右子树右子树右子树右子树根根根根a b c d e f gc b d a e g f例如例如: :
23、aab bccddeeffggabcdefg先序序列中序序列结论：由二叉树的前序和中序序列或后序和结论：由二叉树的前序和中序序列或后序和中序序列能惟一确定一棵二叉树，但由前序中序序列能惟一确定一棵二叉树，但由前序后序序列却不一定能惟一确定一棵二叉树。后序序列却不一定能惟一确定一棵二叉树。问：先序遍历：问：先序遍历：ABDGCEF 中序遍历：中序遍历：DGBAECF 后序遍历：后序遍历：GDBEFCA1.已知一棵树的先根和中根遍历次序如下：已知一棵树的先根和中根遍历次序如下： a b e f g c d h I e f g b c h I d a试画出此树，并画出转化后的二叉树，以及此试画出此树
24、，并画出转化后的二叉树，以及此二叉树的后序线索二叉树。二叉树的后序线索二叉树。 2.一棵完全二叉树按层次遍历的序列是一棵完全二叉树按层次遍历的序列是ABCDEFGHI，则在先序遍历中结点则在先序遍历中结点E的的直接前驱是直接前驱是 I ，后序遍历中结点，后序遍历中结点B的直接后继是的直接后继是 F 。3、试找出分别满足下面条件的所有二叉树、试找出分别满足下面条件的所有二叉树（1）前序序列和中序序列相同）前序序列和中序序列相同（2）中序序列和后序序列相同）中序序列和后序序列相同（3）前序序列和后序序列相同）前序序列和后序序列相同（4）前序、中序、后序序列均相同）前序、中序、后序序列均相同4、试采
25、用顺序存储方法和链式存储方法分别画出下、试采用顺序存储方法和链式存储方法分别画出下列各二叉树的存储结构，并写出前、中后序序列。列各二叉树的存储结构，并写出前、中后序序列。6.3.26.3.2 线索二叉树线索二叉树（重要）（重要）当以二叉链表作为存储结构时当以二叉链表作为存储结构时, ,只能找到结点的左只能找到结点的左右孩子的信息右孩子的信息, ,而不能在结点的任一序列的前驱与而不能在结点的任一序列的前驱与后继信息后继信息, ,这种信息只有在遍历的这种信息只有在遍历的动态动态过程中才能过程中才能得到；并且为了能保存遍历过程中得到的信息得到；并且为了能保存遍历过程中得到的信息, ,可可增加标志域增
26、加标志域; ;任何包括任何包括n n个结点的二叉树中，个结点的二叉树中，2 2n n个指针中只有个指针中只有n n - 1- 1个用来指示结点的左、右子女，而另外个用来指示结点的左、右子女，而另外n + 1n + 1个为空个为空解决方法：用指向结点在对称序下的前驱结点或解决方法：用指向结点在对称序下的前驱结点或后继结点的指针来代替这些空的指针，这种附加后继结点的指针来代替这些空的指针，这种附加的指针称作的指针称作“线索线索”infoltagrtag rlinkllinkltag 0:指针,指向结点的左子女1:线索,指向结点的前趋结点rtag 0:指针,指向结点的右子女1:线索,指向结点的后继结
27、点指向该线性序列中的“前驱”和 “后继” 的指针指针，称作“线索线索”与其相应的二叉树，称作 “线索二叉树线索二叉树”包含 “线索” 的存储结构，称作 “线索链表线索链表”A B C D E F G H K D C B E typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;线索链表的类型描述： typedef enum Link, Thread PointerThr; / Lin
28、k=0:指针，Thread=1:线索在中序线索二叉树中找：在中序线索二叉树中找： 叶子结点：右链域是线索，直接找到后继叶子结点：右链域是线索，直接找到后继后继后继 非终端结点：后继是遍历其右子树时访问的第一非终端结点：后继是遍历其右子树时访问的第一 个结点（右子树中最左下的结点）个结点（右子树中最左下的结点） 左标志位为左标志位为1，则左链域为线索即为前驱，则左链域为线索即为前驱前驱前驱 遍历左子树时最后访问的一个结点即左子树中最右遍历左子树时最后访问的一个结点即左子树中最右 下的结点下的结点 试画出如图所示的二叉树的前序、中序和后序相应的试画出如图所示的二叉树的前序、中序和后序相应的线索链表
29、。线索链表。6.4 树和森林树和森林6.4.1树的存储结构树的存储结构树树三种存储结构三种存储结构一、双亲表示法一、双亲表示法: #define MAX_TREE_SIZE 100结点结构结点结构: typedef struct PTNode Elem data; int parent; / 双亲位置域双亲位置域 PTNode;树结构树结构: typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数根结点的位置和结点个数 PTree;优点：优点：便于找双亲结点便于找双亲结点及根结点。及根结点。缺点：缺点：求孩子结点时需求
30、孩子结点时需遍历整个结构。遍历整个结构。二、孩子链表表示法二、孩子链表表示法:孩子结点结构孩子结点结构: typedef struct CTNode int child; struct CTNode *next; *ChildPtr;双亲结点结构双亲结点结构 typedef struct Elem data; ChildPtr firstchild; / 孩子链的头指针孩子链的头指针 CTBox;树结构树结构: typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置结点数和根结点的位置 CTree;优点：优点：求孩子结点时
31、很方便。求孩子结点时很方便。缺点：缺点：不适用于找双亲结点不适用于找双亲结点三、树的二叉链表三、树的二叉链表(孩子孩子-兄弟）存储表示法兄弟）存储表示法Typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, CSTree;优点：便于实现树的各种操作。优点：便于实现树的各种操作。习题：画出如下各树的三种存储结构。习题：画出如下各树的三种存储结构。6.4.2森林与二叉树的转换森林与二叉树的转换1、则、则由森林转换成二叉树由森林转换成二叉树的转换规则为的转换规则为: 若若 F = ，则
32、则 B = ;否则，否则， 由由 ROOT( T1 ) 对应得到对应得到 Node(root); 由由 (t11, t12, , t1m ) 对应得到对应得到 LBT; 由由 (T2, T3, Tn ) 对应得到对应得到 RBT.2、由由二叉树转换为森林二叉树转换为森林的转换规则为的转换规则为: 若若 B = , 则则 F = ;否则，否则，由由 Node(root) 对应得到对应得到 ROOT( T1 );由由LBT 对应得到对应得到 ( t11, t12, ，t1m);由由RBT 对应得到对应得到 (T2, T3, , Tn)由此，树的各种操作均可转化成二叉树的操作由此，树的各种操作均可转
33、化成二叉树的操作来完成来完成换言之，和树对应的二叉树，其左、右子树的换言之，和树对应的二叉树，其左、右子树的概念改变成：概念改变成：左是孩子，右是兄弟左是孩子，右是兄弟6.4.3树和森林的遍历树和森林的遍历树的遍历可有三条搜索路径树的遍历可有三条搜索路径:先根先根(次序次序)遍历遍历: 若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根后根(次序次序)遍历遍历: 若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历按层次遍历: 若树不空，则自上而下自左至右访问树中每个结点若树
34、不空，则自上而下自左至右访问树中每个结点。森林的遍历森林的遍历 先序遍历先序遍历(对森林中的每一棵树进行先根遍历对森林中的每一棵树进行先根遍历)若森林不空，则若森林不空，则 访问森林中第一棵树的根结点访问森林中第一棵树的根结点; 先序遍历森林中第一棵树的子树森林先序遍历森林中第一棵树的子树森林; 先序遍历森林中先序遍历森林中(除第一棵树之外除第一棵树之外)其余树构成的森林。其余树构成的森林。 中序遍历中序遍历(对森林中的每一棵树进行后根遍历对森林中的每一棵树进行后根遍历)若森林不空，则若森林不空，则 中序遍历森林中第一棵树的子树森林中序遍历森林中第一棵树的子树森林; 访问森林中第一棵树的根结点
35、访问森林中第一棵树的根结点; 中序遍历森林中中序遍历森林中(除第一棵树之外除第一棵树之外)其余树构成的森林。其余树构成的森林。习题：对图所示的森林：习题：对图所示的森林：1) 求各树的前序序列和后序序列；求各树的前序序列和后序序列；2) 求森林的前序序列和后序序列；求森林的前序序列和后序序列；3) 将此森林转换为相应的二叉树；将此森林转换为相应的二叉树；6.6 最优二叉树哈夫曼树1哈夫曼树的基本概念 最优二叉树，也称哈夫曼（最优二叉树，也称哈夫曼（Haffman）树，是指对于一树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度组带有确定权值的叶结点，构造的具有最小带权路径长度的二
36、叉树。的二叉树。 二叉树的路径长度是指由根结点到所有叶结点的路径长二叉树的路径长度是指由根结点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值，则可度之和。如果二叉树中的叶结点都具有一定的权值，则可将这一概念加以推广。设二叉树具有将这一概念加以推广。设二叉树具有n个带权值的叶结点，个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为：乘积之和叫做二叉树的带权路径长度，记为： WPL WkL Lk 其中其中Wk为第为第k k个叶结点的权值，个叶结点的权值，L Lk 为第为第k个
37、叶结点的路个叶结点的路径长度径长度。 在给定一组具有确定权值的叶结点，可以构造出不同在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出的带权二叉树。例如，给出4个叶结点，设其权值分别个叶结点，设其权值分别为为1，3，5，7，我们可以构造出形状不同的多个二叉树，我们可以构造出形状不同的多个二叉树。下图给出了其中。下图给出了其中5个不同形状的二叉树，其带权路径个不同形状的二叉树，其带权路径长度分别为：长度分别为： （a）WPL1232527232 （b）WPL1333527129 （c）WPL1233537133 （d）WPL7353321143 （e）WPL715233132
38、9 如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？根据如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。哈夫曼（哈夫曼（Haffman）依据这一特点提出了一种方法，这种方法的依据这一特点提出了一种方法，这种方法的基本思想是：基本思想是： （1）由给定的）由给定的n个权值个权值W1，W2，Wn构造构造n棵只有一个棵只有一个叶结点的二叉树，从而得到一个二叉树的集合叶结点的
39、二叉树，从而得到一个二叉树的集合FT1，T2，Tn； （2）在在F中选取根结点的权值最小和次小的两棵二叉树作为左中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；其左、右子树根结点权值之和； （3）在集合）在集合F中删除作为左、右子树的两棵二叉树，并将新建中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合立的二叉树加入到集合F中；中； （4）重复（）重复（2）（）（3）两步，当）两步，当F中只剩下一棵二叉树时，这棵中只剩下一棵二叉树时，这棵二叉树便
40、是所要建立的哈夫曼树。二叉树便是所要建立的哈夫曼树。 下图给出前面提到的叶结点权值集合为下图给出前面提到的叶结点权值集合为W1，3，5，7的哈夫曼树的构造过程。可以计算出其带权路的哈夫曼树的构造过程。可以计算出其带权路径长度为径长度为29，由此可见，对于同一组给定叶结点所构，由此可见，对于同一组给定叶结点所构造的哈夫曼树，树的形状可能不同，但带权路径长度造的哈夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的。值是相同的，一定是最小的。6.6.2哈夫曼树在编码问题中的应用哈夫曼树在编码问题中的应用 在数据通讯中，经常需要将传送的文字转换成由二进制字符在数据通讯中，经常需要将传送的
41、文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA，电文中只含有电文中只含有A，B，C，D四种字符，若这四种字四种字符，若这四种字符 采 用 表符 采 用 表 6 . 2 ( a ) 所 示 的 编 码 ， 则 电 文 的 代 码 为所 示 的 编 码 ， 则 电 文 的 代 码 为000010000100100111000，长度为，长度为21。在传送电文时，我们总是希。在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短，显然，这种望传送时间尽可能短，这就要求电文代码尽可能
42、短，显然，这种编码方案产生的电文代码不够短。表编码方案产生的电文代码不够短。表6.2 (b)所示为另一种编码方所示为另一种编码方案 ， 用 此 编 码 对 上 述 电 文 进 行 编 码 所 建 立 的 代 码 为案 ， 用 此 编 码 对 上 述 电 文 进 行 编 码 所 建 立 的 代 码 为00010010101100，长度为，长度为14。在这种编码方案中，四种字符的编。在这种编码方案中，四种字符的编码均为两位，是一种等长编码。如果在编码时考虑字符出现的频码均为两位，是一种等长编码。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字率，让出现频率高的字
43、符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。如当字符更短。如当字符A，B，C，D采用表采用表6.2 (c)所示的编码时，上述电所示的编码时，上述电文的代码为文的代码为0110010101110，长度仅为，长度仅为13。定义：前缀编码定义：前缀编码指的是，任何一个字符的编码都不是同一字符集任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀中另一个字符的编码的前缀。例：6-2习题：习题：1、下述编码哪一组不是前缀编码？、下述编码哪一组不是前缀编码？00，01，10，11，0，1，0
44、0，11，0,10,110,111 2、假设用于通信的电文由字符集体、假设用于通信的电文由字符集体a,b,c,d,e,f,g,h中的中的字母构成，这字母构成，这8个字母在电文中出现的概率分别为个字母在电文中出现的概率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。为这为这8个字母设计哈夫曼编码个字母设计哈夫曼编码解：设权解：设权w的值为（的值为（7,19,2,6,32,3,21,10）n=8,m=15，按，按上述构造赫夫曼树。上述构造赫夫曼树。 0 1 0 1 0 1 0 1 0 1 0 1 36 0 1 0 1 0 1 01 0 1 0 1 0 1 0 1
