数据结构06课件.ppt

第6章 树和二叉树 6.5.2 路径长度和最优二叉树（哈夫曼树） 哈夫曼（Huffman）树又称最优二叉树或最优搜索树，是一种带权路径长度最短的二叉树。 在许多应用中，常常赋给树中结点一个有某种意义的实数，称此实数为该结点的权。从树根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度(WPL)。 树中所有叶子结点的带权路径长度之和称为该树的带权路径长度，通常记为： 两结点间的路径：从一结点到另一结点所经过的结点序列 路径长度：路径上的分支树 树的路径长度：从根到每一结点的路径长度之和 2 7 6 3 4 1 5 例 ⑴-⑵-⑸为结点1到5之间的路径，其路径长度为2， 树的路径长度=l12 +l13+ l14 +l15+ l16 +l17 =1+1+2+2+2+2=10 完全二叉树是路径长度最短的二叉树。 考虑带权时：设树中有m个叶结点，每个叶结点带一个权值wｉ且根到叶结点i的路径长度为 Li (ｉ=1，2，．． m），则树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。 　　　　　　 Ｍ　　　 即：ＷＰＬ＝∑ ＷｋＬｋ 　　　　　　Ｋ＝１　 例如，给定4个叶结点，设权值分别为1，3，5，7，据此可以构造出形状不同的4棵二叉树，如图6-19所示。它们的带权路径长度分别为： (a) WPL=1×2+3×2+5×2+7×2=32 (b) WPL=1×2+3×3+5×3+7×l=33 (c) WPL=7×3+5×3+3×2+1×1=43 (d) WPL=1×3+3×3+5×2+7×1=29 WPL最小的二叉树是最优二叉树(Huffman 树)，图6-19(d)所示。 图6-19 由4个结点构成的不同的带权二叉树 第0层 第1层 第2层 第3层 1．二叉树的路径长度 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路经上的分支数目称为路径长度。树的路径长度是指从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。 2．二叉树的带权路径长度(Weighted Path Length of Tree，简记为WPL) 结点的带权路径长度定义为结点到树根之间的路径长度与该结点上所带权值的乘积。 树的带权路径长度(Weighted Path Length of Tree)是树中所有叶结点的带权路径长度之和，通常记为： 3．最优二叉树或哈夫曼树 哈夫曼树（或最优二叉树）：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树。 结论: ① 当叶子上的权值均相同时，完全二叉树一定是最优二叉树。否则完全二叉树不一定是最优二叉树。 ② 在最优二叉树中，权值越大的叶子离根越近。 ③ 最优二叉树的形态不唯一，但WPL最小。 3．最优二叉树或哈夫曼树 哈夫曼树（或最优二叉树）：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树。 结论: ① 当叶子上的权值均相同时，完全二叉树一定是最优二叉树。否则完全二叉树不一定是最优二叉树。 ② 在最优二叉树中，权值越大的叶子离根越近。 ③ 最优二叉树的形态不唯一，但WPL最小。 6.5.3 构造最优二叉树： 1．哈夫曼算法 哈夫曼算法的基本思想是： (1) 以权值分别为W1,W2．．．Ｗｎ的ｎ各结点，构成n棵二叉树T1,T2,．．．Tn并组成森林F={T1,T2,．．．Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点； (2) 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值=左右孩子权值之和，叶结点的权值= Wi） (3) 从F中删除这两棵二叉树，同时将新二叉树加入到F中; (4) 重复(2)．(３)直到F中只含一棵二叉树为止，这棵二叉树就是Huffman 树。 例如，给定权值集合{5，15，40，30，10}构造哈夫曼树的过程如图6-21所示，其中最优的带权路径长度为：WTL＝(5＋10)×4＋15×3＋30×2＋40＝205。由图6-21可以看出，哈夫曼树的结点的度数为0或2，没有度为1的结点。 图6-21 哈夫曼树构造过程 2．哈夫曼树的存储结构及哈夫曼算法的实现 (1) 哈夫曼树的存储结构 用大小为2n-1的一维数组来存储哈夫曼树中的结点，其存储结构为： #d