第五章树和二叉树

《第五章树和二叉树》由会员分享，可在线阅读，更多相关《第五章树和二叉树（83页珍藏版）》请在金锄头文库上搜索。

1、第五章第五章 树和二叉树树和二叉树5.1树与树林5.2树和树林的存储表示 5.3二 叉 树 5.4二叉树的存储表示5.5哈夫曼算法及其应用1张乃孝 算法与数据结构C语言描述线性结构和非线性结构。 树形结构是以分支关系定义的层次结构，在现实世界中广泛存在，在计算机领域中也有广泛应用。 本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关系。2张乃孝 算法与数据结构C语言描述5.1 5.1 树与树林树与树林 5.1.1 5.1.1 树的定义树的定义 5.1.2 5.1.2 基本术语基本术语 5.1.3 5.1.3 树林树林 5.1.4 5.1.4 树的基本运算树的基本运算

2、5.1.5 5.1.5 树的周游树的周游 5.1.6 5.1.6 树林的周游树林的周游3张乃孝 算法与数据结构C语言描述5.1.1 5.1.1 树的定义树的定义树树(Tree)的例子：一个家族。A有子女B,C； B和 C分别有子女D,E,F和G,H;E有 子女I , J。 T=(N,R) ,其中 N=A, B, C, D, E, F, G, H, I, J R= A, B, A, C, B, D , B, E, B, F, C, G, C, H, E, I, E, J 4张乃孝 算法与数据结构C语言描述树的表示方法：树的表示方法：(c ) 凹入表（a）树形表示ABCDEFIJGH5张乃孝 算法

3、与数据结构C语言描述(A(B(D)(E(I)(J)(C(G)(H)(d) 嵌套括号表示法CDEIJFGHAB(b) 文氏图6张乃孝 算法与数据结构C语言描述 树树(Tree)：是包括n(n=0)个结点结点的有限集T。当T非空时，满足：（1）有且仅有一个特别标出的称为根根的 结点；（2）除除根结点根结点外，其余结点可分为m（m=0） 个互不相交非空的有限集T1, T2, , Tm, 其中 每一个集合本身又是一棵树，称为根的子树子树 (Subtree)。树的递归定义：树的递归定义：空树空树：不包括任何结点的树。7张乃孝 算法与数据结构C语言描述树结构的特点：树结构的特点：（1）树的根的结点没前驱结

4、点，除了根结点之外 的所有结点都有且只有一个前驱结点；（2）树的结点可以有零个或多个后继结点。 树结构描述的是层次关系。8张乃孝 算法与数据结构C语言描述5.1.2 5.1.2 基本术语基本术语 (a) 树t (b) 树t 图5.2 树t和树t 9张乃孝 算法与数据结构C语言描述 父结点父结点，子结点，子结点，边边 若结点y是结点x的一棵子树的根，则x称作y的父结父结点点（或父母）；y称作x的子结点子结点（或子女）；有序对称作从x到y的边边。例如树t中，C是E的父结点，E是C的子结点，是从C到E的边（它对应着图中的有向线段CE）。 兄弟结点兄弟结点具有同一父母的结点彼此称作兄弟兄弟。树t中B，

5、C，D互为兄弟，F，G互为兄弟，等等。注意，E和F并不是兄弟。 10张乃孝 算法与数据结构C语言描述 祖先祖先，子孙子孙若结点y在以结点x为根的一个子树（或树）中，且yx，则称x是y的祖先祖先，y是x的子孙子孙。例如树t中，A是其它各结点的祖先；C是E，H，I，J的祖先。 路径路径，路径长度路径长度如果x是y的一个祖先，又有xx0，x1，xny，满足xi（i0，1，n-1）为xi+1的父结点，则称x0，x1，xn为从x到y的一条路径路径。n称为这条路径的长度路径的长度。路径中相邻的两个结点可以表示成一条边。 例如树t中A，C，E，I，J是从A到J的一条路径，其长度为4。 11张乃孝 算法与数据

6、结构C语言描述 结点的层数结点的层数规定根的层数根的层数为0，其余结点的层数结点的层数等于其父母结点的层数加1。例如t中，0层的结点是A，1层的结点有B，C，D，4层的结点是J。 树的深度或高度树的深度或高度树中结点的最大层数称为树的深度树的深度或树的高度树的高度。 例如树t中，树的深度为4。 12张乃孝 算法与数据结构C语言描述 结点的度数结点的度数、树的度数树的度数结点的子女个数叫作结点的度数度数。树中度数最大的结点的度数叫作树的度数树的度数。例如t中A，C，E，J的度数分别为3，1，2，0；t的度数为3 树叶树叶、分支结点分支结点度数为0的结点称作树叶树叶或终端结点终端结点；度数大于0的

7、结点称作分支结点分支结点或非终端结点非终端结点。例如树t中B，F，G，H，J都是树叶，其余结点都是分支结点。13张乃孝 算法与数据结构C语言描述 无序树无序树、有序树有序树对子树的次序不加区别的树叫作无序树无序树。对子树之间的次序加以区别的树叫作有序树有序树。例如在图5.2中，按无序树的概念t和t是同一棵树，按有序树的概念则是不同的树，本章讨论的树一般是有序树。 结点的次序结点的次序 在有序树中可以从左到右地规定结点的次序次序。按从左到右的顺序，我们可以把一个结点的最左边的子结点简称为最左子结点最左子结点，或直接称为长子长子，而把长子右边的结点称为次子次子。例如在t中结点B是结点A的长子，结点

8、C是结点A的次子，是结点B的兄弟。 14张乃孝 算法与数据结构C语言描述树林树林：是m（m=0）棵互不相交的树所组成的集合。就逻辑结构而言，任何一棵树是一个二元组二元组Tree=(root,F) , 其中root称为树的根结点，F是m（m0）棵子树构成的树林，F=(T1, T2,Tm), 其中Ti=(ri,Fi)称作根root的第i棵子树；当m0时，在树根和其子树林之间存在下列关系: RF= | i=1,2,m, m05.1.3 5.1.3 树林树林15张乃孝 算法与数据结构C语言描述5.1.4 5.1.4 树的基本运算树的基本运算创建一棵空树Tree createTree( Node p,

9、Tree t1, Tree t2, , Tree ti ) i=1, 2, 3, 判断某棵树是否为空int isNull ( Tree t )求树中的根结点，若为空树，则返回一特殊值Node root ( Tree t ) 求某个指定结点的父结点，当指定结点为根时，返回一特殊值Node parent ( Node p ) 16张乃孝 算法与数据结构C语言描述 求树中某个指定结点的最左子结点，当指定结点为树叶时，返回一特殊值Node leftChild ( Node p ) 求树中某个指定结点的右兄弟结点，当指定结点没有右兄弟时，返回一特殊值Node rightSibling ( Node p

10、) 树的周游：即按某种方式访问树中的所有结点，并使每个结点恰好被访问一次。17张乃孝 算法与数据结构C语言描述5.1.5 5.1.5 树的周游树的周游1. 周游的定义:按某一规律系统的访问树中的所有 结点，并使每个结点恰好被访问一次。2. 周游的方法：按深度方向和按宽度方向周游。 （I）按深度方向（以右图为例）a. 先根次序b. 中根次序c. 后根次序18张乃孝 算法与数据结构C语言描述a. 先根次序 (1,2,3,5,8,9,6,10,4,7) （1） 访问根结点； （2）从左到右按先根次序周游根结点的每棵子树。 b. 中根次序 (2,1,8,5,9,3,10,6,7,4) （1）按中根次序

11、周游根结点的最左子树； （2）访问根结点； （3）从左到右按中根次序周游根结点的其它各子树。c. 后根次序 (2,8,9,5,10,6,3,7,4,1) （1）从左到右按后根次序周游根结点的每棵子树; （2）访问根结点。19张乃孝 算法与数据结构C语言描述（II）按宽度方向周游 先访问层数为0的结点，然后从左到右逐个访 问层数为1的结点，依此类推，直到访问完树中 的全部结点。 层次序列（1，2，3，4，5，6，7，8，9，10）20张乃孝 算法与数据结构C语言描述1. 先根（A, B, C, K, D, E, H, F, J, G )2. 后根 ( B, K, C, A, H, E, J, F

12、, G, D )5.1.6 5.1.6 树林的周游树林的周游21张乃孝 算法与数据结构C语言描述5.2 5.2 树和树林的存储表示树和树林的存储表示 5.2.1 5.2.1 树的存储表示树的存储表示 5.2.2 5.2.2 树林的存储表示树林的存储表示 5.2.3 5.2.3 树和树林的其它表示法树和树林的其它表示法* *22张乃孝 算法与数据结构C语言描述5.2.1 5.2.1 树的存储表示树的存储表示 树的父指针表示法 树的子表表示法 树的长子-兄弟表示法23张乃孝 算法与数据结构C语言描述struct ParTreeNode/* 树中结点结构 */ DataTypeinfo; /* 结点

13、中的元素 */intparent; /* 结点的父结点位置 */;struct ParTree struct ParTreeNode nodelistMAXNUM; /* 存放树中的结点 */ int n; /* 树中结点的个数 */; typedef struct ParTree *PParTree;树的父指针表示法用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。结构类型如下：24张乃孝 算法与数据结构C语言描述 优点：a)容易找到父结点及其所有的祖先； b)能找到结点的子女和兄弟； 缺点：a)没有表示出结点之间的左右次序； b)找结点的子女和兄弟比较费事。改进方法：按一种

14、周游次序在数组中存放结点,。常见的一种方法是依次存放树的先根序列，如下图：25张乃孝 算法与数据结构C语言描述(a) (b) 图5.5 一棵树的父指针表示 26张乃孝 算法与数据结构C语言描述树的子表表示法 结点表中的每一元素又包含一个子表，存放该结点的所有子结点。结点表顺序存放，子表用链接表示。struct EdgeNode /* 子表中节点的结构 */intnodeposition;struct EdgeNode*link;struct ChiTreeNode /* 结点表中节点的结构 */DataTypeinfo;struct EdgeNode*children;27张乃孝 算法与数据结

15、构C语言描述子表表示的树结构定义如下：struct ChiTree /* 树结构 */ struct ChiTreeNode nodelistMAXNUM; introot; /* 根结点的位置 */ intn; /* 结点的个数 */typedef struct ChiTree * PChiTree; 求某个结点的最左子女运算很容易实现，找到结点的全部子女也很容易，但求某个结点的父母和右兄弟实现起来比较费事。另一个缺点是：合并若干个子树构成一个新树时（createTree_chitree操作）也要考虑多个结点表的合并问题，由于这些结点表通常用顺序方式表示，所以合并起来比较麻烦。 28张乃孝

16、算法与数据结构C语言描述 1 7 2 3 4 6 8 9 5 图5.6 树的子表表示法29张乃孝 算法与数据结构C语言描述 在树的每个结点中，除信息域外，增加指向其最左子女和右兄弟的指针。struct CSNode; /* 树中结点结构 */typedef struct CSNode *PCSNode;/* 结点的指针类型 */struct CSNode /* 结点结构定义 */ DataType info;/* 结点中的元素 */PCSNode lchild; /* 结点的最左子女的指针 */PCSNode rsibling;/* 结点的右兄弟的指针 */; typedef struct C

17、SNode *CSTree; /* 树类型定义 */ 树的长子-兄弟表示法30张乃孝 算法与数据结构C语言描述 t a b d c e h i j f g 图5.7 树的长子兄弟表法31张乃孝 算法与数据结构C语言描述5.2.2 5.2.2 树林的存储表示树林的存储表示 父指针表示法 子表表示法 长子-兄弟表示法32张乃孝 算法与数据结构C语言描述树林的父结点表示方法 33张乃孝 算法与数据结构C语言描述 1 2 3 5 9 8 6 7 树林的子表表示法34张乃孝 算法与数据结构C语言描述 t A B D C E H J K F G 树林的长子兄弟表示法35张乃孝 算法与数据结构C语言描述5.

18、3 5.3 二叉树二叉树 5.3.1 5.3.1 二叉树的基本概念二叉树的基本概念 5.3.2 5.3.2 二叉树的性质二叉树的性质 5.3.3 5.3.3 二叉树的基本运算二叉树的基本运算 5.3.4 5.3.4 二叉树的周游二叉树的周游 5.3.5 5.3.5 树、树林与二叉树的转换树、树林与二叉树的转换36张乃孝 算法与数据结构C语言描述二叉树： 它是结点的有限集合，这个集合或者为空集或者由一个根及两棵不相交的分别称作这个根的“左子树”和“右子树”的二叉树组成。 它的每一个结点至多有两棵子树，并且子树有左右之分，不能随意颠倒。5.3.1 5.3.1 二叉树的基本概念二叉树的基本概念37张

19、乃孝 算法与数据结构C语言描述二叉树的基本形态：左子树右子树右子树左子树（1）空二叉树（2）只有一个根结点（3）有根结点 和左子树（4）有根结点 和右子树（5）有根结点 和左，右子树38张乃孝 算法与数据结构C语言描述 二叉树不是树的特殊情形，它们是两个概念。 树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 （3）和（4）是两棵不同的二叉树，但作为树，它们是相同的。 在二叉树中可定义类似树中的概念。39张乃孝 算法与数据结构C语言描述 满满二二叉叉树树：如果一棵二叉树的任何结点或者是树叶，或者有两棵非

20、空子树，则此二叉树称作“满二叉树”。 完完全全二二叉叉树树：如果一棵二叉树至多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为“完全二叉树”。完全二叉树不一定是满二叉树。40张乃孝 算法与数据结构C语言描述满二叉树完全二叉树41张乃孝 算法与数据结构C语言描述扩充二叉树扩充二叉树 ： 把原二叉树的结点都变为度数为2的分支结点，也就是说，如果原结点的度数为2，则不变，度数为1，则增加一个分支，度数为0（树叶）增加两个分支。 42张乃孝 算法与数据结构C语言描述在扩充的二叉树里，新增加的外部结点的个数比原来的内部结点个数多1。 “外部路径长度”

21、E：在扩充的二叉树里从根到每个外部结点的路径长度之和。“内部路径长度”I：在扩充的二叉树里从根到每个内部结点的路径长度之和。 E = I + 2n 其中，n是内部结点的个数。43张乃孝 算法与数据结构C语言描述证明：当n=1时，I=0, E=2, 此等式成立。 设有n个内部结点的扩充二叉树，下式成立。 En=In+2n (1) 对于 n+1 个内部结点的扩充二叉树，去掉一个 作为原来二叉树路径长度为K的内部结点，内部路径长度变为： In=In+1-K (2) 外部路径长度变为：En=En+1-2(K+1)+K= En+1 -K-2 即： En+1= En+K+2 En+1= (In+2n) +

22、K+2= (In+1-K) +2n+K+2= In+1+2(n+1) 代入（1） 代入（2）44张乃孝 算法与数据结构C语言描述abceef45张乃孝 算法与数据结构C语言描述性质性质1. 在非空二叉树的第i层上至多有2i个结点（i0）。归纳： i=0, 结点数=1=20 . 假设对于j(0j i), 结点数至多有2j . 对于i=j+1, 结点数至多为 2* 2j=2j+1 .性质性质2. 深度为k的二叉树至多有2k+1-1个结点（k 0）。 K k M= mi 2i = 2k+1-1 i=0 i=0 20 + 21 + 22 + 2k5.3.2 5.3.2 二叉树的性质二叉树的性质46张乃

23、孝 算法与数据结构C语言描述性质性质3. 对任何一棵非空二叉树T，如果叶结点数 为n0， 度为2的结点数为n2，则n0=n2+1。 n0+n1+n2 = 所有 结点的度数和+1 = n1+ 2*n2 +1 性质性质4. 具有n个结点的完全二叉树的深度k为log2n . n=20+21+22+2k-1+mk =2k-1+mk 2k-1n 2k+1-1 2k n 2k+1 k log2n k+1 k= log2n 47张乃孝 算法与数据结构C语言描述性质性质5. 如果对一棵有n个结点的完全二叉树按层次次序 从1开始编号，则对任一结点i（1 in)，有： 1）i=1，序号结点i是根；i1, 其双亲结

24、点是 i/2 。 2）2i n，序号为i的结点的左子女结点的序号为2i； 2in ,序号为i的结点无左子女。 3）2i+1 n，序号为i的结点的右子女结点的序号 为2i+1; 2i+1 n,序号为i的结点无右子女。48张乃孝 算法与数据结构C语言描述性质5的证明：对于（2）和（3） 当i=1时， 2i=2 n ，左子女结点的序号为2。2i+1=3 n， 右子女结点的序号为3。 假设对于序号为j的结点，命题成立。 对于i=j+1，其左子女结点的序号等于j的右子女结点的序号加1，即：2j+1+1=2(j+1) 其右子女结点的序号等于：2(j+1)+1根据（2）和（3），知的父结点为i/2. 完全二

25、叉树的层次序列，反映了它的结构。49张乃孝 算法与数据结构C语言描述123jj+1 2j 2j+1 2(j+1) 2(j+1)+150张乃孝 算法与数据结构C语言描述5.3.3 5.3.3 二叉树的基本运算二叉树的基本运算创建一棵空二叉树；判断某棵二叉树是否为空；求二叉树的根结点，若为空，则返回一特殊值；求二叉树中某个指定结点的父结点，当指定结点为根时，返回一特殊值；求二叉树中某个指定结点的左子女结点，当指定结点没有左子女时，返回一特殊值；求二叉树中某个指定结点的右子女结点，当指定结点没有右子女时，返回一特殊值；二叉树的周游。51张乃孝 算法与数据结构C语言描述5.3.4 5.3.4 二叉树的

26、周游二叉树的周游二叉树的周游二叉树的周游(Traversing Binary Tree)： 按某条搜索路径访问二叉树中的所有结点 ，使得每个结点被访问一次且仅被访问一次。三种方式： 先根次序 (DLR) 对称序 (LDR) 后根次序 (LRD)DLR52张乃孝 算法与数据结构C语言描述ABDCEFIHG 图5.15 二叉树先根次序A B D C E G F H I 后根次序D B G E H I F C A 对称序（中根次序）D B A E G C H F I53张乃孝 算法与数据结构C语言描述 对右图进行先根、后根和中根次序周游得到如下的结点序列： 先根：-ab+cd 前缀表示 后根：ab-

27、cd+ 后缀表示 (波兰表示法) 对称序：a-b c+d 中缀表示-+abcd图 5.16 表达式的二叉树表示54张乃孝 算法与数据结构C语言描述二叉树的周游算法二叉树的周游算法一.递归算法先根次序中根次序后根次序二. 非递归算法 (用自定义的栈来代替系统的栈)先根次序中根次序后根次序 1 255张乃孝 算法与数据结构C语言描述5.3.5 5.3.5 树、树林与二叉树的转换树、树林与二叉树的转换 1. 树、树林转换为二叉树执行步骤：（1）在所有相邻的兄弟结点之间连一条线；（2）对每个非终端结点，只保留它到其最左子女的 连线，删去它与其它子女的连线；（3）以根结点为轴心，将整棵树进行旋转。树、树

28、林树、树林 二叉树二叉树56张乃孝 算法与数据结构C语言描述ABCKDEFGHJ图5.20 树林转换为二叉树57张乃孝 算法与数据结构C语言描述2. 二叉树转换为树、树林执行步骤：（1）若某结点是其父母的左子女，则把该结点 的右子女，右子女的右子女， ,都与 该结点的父母用线连接起来； （2）去掉原二叉树中所有父母到右子女的连线。58张乃孝 算法与数据结构C语言描述ABDCEKHFJG图 5.22 二叉树转换为树林59张乃孝 算法与数据结构C语言描述5.4 5.4 二叉树的存储表示 5.4.1 5.4.1 顺序表示顺序表示 5.4.2 5.4.2 链接表示链接表示 5.4.3 5.4.3 二叉

29、树的生成二叉树的生成 5.4.4 5.4.4 线索二叉树线索二叉树* *60张乃孝 算法与数据结构C语言描述 用一组地址连续的存储单元按层次次序依次存储完全二叉树的结点。完全二叉树的层次序列反映了它的层次结构。5.4.1 5.4.1 顺序表示顺序表示ABCGFEDHIJ A B C D E F G H I J 下标 0 1 2 3 4 5 6 7 8 961张乃孝 算法与数据结构C语言描述 对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中。图514 一般二叉树及其顺序表示62张乃孝 算法与数据结构C语言描述采用顺序表示，类型声明如下： struct Seq

30、BTree /* 顺序树类型定义 */ DataType nodelistMAXNODE;int n;/* 改造成完全二叉树后，结点的个数 */ ；typedef struct SeqBTree *PSeqBTree;63张乃孝 算法与数据结构C语言描述5.4.2 5.4.2 链接表示链接表示 二叉树的链接表示是指用一个链表来存储一棵二叉树，二叉树中的每一个结点用链表中的一个链结点来存储，最常用的链接表示方式是左-右指针表示法（llink-rlink表示法，也称做二叉链表），这种表示法在每个链结点中除存储结点本身的数据外，再设置两个指针字段：llink和rlink，分别存放结点的左子女和右子女

31、所在链结点的存储地址，当结点的某个子女为空时，则相应的指针为空指针。 64张乃孝 算法与数据结构C语言描述struct BinTreeNode;/* 二叉树中结点 */typedef struct BinTreeNode *PBinTreeNode;/* 结点的指针类型 */struct BinTreeNode DataType info;/* 数据域 */PBinTreeNode llink;/* 指向左子女 */PBinTreeNode rlink;/* 指向右子女 */;typedef struct BinTreeNode *BinTree; typedef BinTree *PBinT

32、ree; 65张乃孝 算法与数据结构C语言描述ABDCEFIHGt A B C E F I H G D 图5.15 二叉树的二叉链表表示66张乃孝 算法与数据结构C语言描述tA B D C E F I H G 图5.15 三叉链表表示67张乃孝 算法与数据结构C语言描述5.4.3 5.4.3 二叉树的生成二叉树的生成 周游是二叉树各种操作的基础，可以在周游过程中进行各种操作，如可以在周游过程中生成结点，从而建立一棵二叉树。 例：读入字符序列： ABDCEGFHI建立图5.13所示的二叉树，其中，表示空结点。算法5.5 按先根序列创建二叉树68张乃孝 算法与数据结构C语言描述t A B C E

33、F I H G D 图5.15 二叉树的二叉链表表示5.4.4 5.4.4 线索二叉树线索二叉树* * 69张乃孝 算法与数据结构C语言描述保存遍历过程中得到的信息以供某些操作使用（1增加两个指针（2利用结构中的空链域，并设立标志。线索线索：指向结点前驱或后继的指针。线索二叉树线索二叉树：加上线索的二叉树。线索化线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。按对称序线索化二叉树按对称序线索化二叉树: :按对称序周游二叉树，周游到那个结点对那个结点加线索。按对称序周游对称序穿线树按对称序周游对称序穿线树: :沿线索周游。70张乃孝 算法与数据结构C语言描述struct ThrTreeN

34、ode;typedef struct ThrTreeNode*PThrTreeNode;struct ThrTreeNode /*结点类型*/ DataType info;PThrTreeNode llink, rlink;int ltag, rtag;typedef struct ThrTreeNode *ThrTree, /*树类型*/typedef ThrTree *PThrTree; /*类型的指针类型*/71张乃孝 算法与数据结构C语言描述Struct SeqStack /*栈元素的类型为PThrTreeNode*/ PThrTreeNode sMAXNODE; int t; ;ty

35、pedef Struct SeqStack *PSeqStack;算法算法5.6 按对称序线索化二叉树按对称序线索化二叉树算法算法5.7 按对称序周游对称序穿线树按对称序周游对称序穿线树72张乃孝 算法与数据结构C语言描述 对称序穿线树里的线索总是指向二叉树中更高层的结点，也就是说是“向上”指的(如下图）。利用该“向上”指的线索我们可以在对称序穿线树里找出指定结点在先根下的后继结点和后根下的前驱结点。73张乃孝 算法与数据结构C语言描述5.5 5.5 哈夫曼算法及其应用 5.5.1 5.5.1 哈夫曼树哈夫曼树 5.5.2 5.5.2 哈夫曼哈夫曼( (Huffman)Huffman)算法算法

36、 5.5.3 5.5.3 哈夫曼编码哈夫曼编码74张乃孝 算法与数据结构C语言描述5.5.1 5.5.1 哈夫曼树哈夫曼树扩充二叉树的外部路径长度：其中：li为从根到第i个外部结点的路径长度，m为外部结点的个数 扩充二叉树的带权的外部路径长度 其中：wi是第i个外部结点的权值，li为从根到第i个外部结点的路径长度，m为外部结点的个数。 75张乃孝 算法与数据结构C语言描述哈夫曼树 假设有一组（无序）实数w1 , w2 , w3 , wm，现要构造一棵以wi（i = 1,2,，m）为权的m个外部结点的扩充的二叉树，使得带权的外部路径长度WPL最小。满足这一要求的扩充二叉树就称为哈夫曼树哈夫曼树或

37、最优二叉树最优二叉树。 例如： 2,3,4,1111423234112113476张乃孝 算法与数据结构C语言描述（1）由给定的m个权值w1,w2,wm构造成m棵二叉树集F=T1,T2,Tm，其中每一棵二叉树Ti中只有一个带权为wi的根结点，且根结点的权值为wi ；（2）在F中选取两棵权值最小的树作为左右子树以构造一棵新的二叉树，且新二叉树的根结点的权值为其左右子树根结点权值之和；（3）在F中删除这两棵树，同时将新得到的二叉树加入F中；（4）重复（2）和（3），直到F中只含一棵树为止。5.5.2 5.5.2 哈夫曼算法哈夫曼算法77张乃孝 算法与数据结构C语言描述2,3,4,112341152

38、394201178张乃孝 算法与数据结构C语言描述哈夫曼(huffman)算法的实现 存储结构：struct HtNode/* 哈夫曼树结点的结构 */ int ww; int parent,llink,rlink;struct HtTree/* 哈夫曼树定义 */struct HtNode htMAXNODE; int root;/* 哈夫曼树根在数组中的下标 */;typedef struct HtTree *PHtTree;79张乃孝 算法与数据结构C语言描述设 d=d1, d2 , , dn w=w1, w2 , , wn d为要编码的字符集合，w为d中各种字符出现的频率。要求：（1）

39、编码总长最短； （2）若di dj , di编码不是dj编码的前缀。5.5.3 5.5.3 哈夫曼编码哈夫曼编码80张乃孝 算法与数据结构C语言描述 用构造哈夫曼树以完成哈夫曼编码： 把d1,d2, dn 作为外部结点，把w1,w2,.,wn作为外部结点的权，构造哈夫曼树。在哈夫曼树中把从每个结点引向其左子女的边上标上0；把从每个结点引向其右子女的边上标上1。 从根结点到叶子结点的路径上的数字拼接起来就是这个叶子结点字符的编码。81张乃孝 算法与数据结构C语言描述例：d=a , b , c , d , e w=50,35,25,20,3050 35 25 20 30 abcde25 20 cd 4530 e 35 b 6550 a9516001010101a:00 b:10 c:010d:011 e:1182张乃孝 算法与数据结构C语言描述小小 结结l树、树林、二叉树的一些基本概念和术语；l二叉链表存储结构l树、二叉树的周游l哈夫曼树的构造方法及应用83张乃孝 算法与数据结构C语言描述