数据结构--第六章树与二叉树.ppt

路径：从一个结点到另一个结点之间的分支 序列。 路径长度：从一个结点到另一个结点所经过 的分支条数。 树的路径长度：树中每个结点与根之间的路径 长度之和（PL）。 a 例： PL(a)=1+1+2+2+2+2=10 b PL(b)=1+1+2+2+3+3=12 一、基本概念： * 带权路径长度：在树形结构中，我们把从树根到某一结点的路径长度与该结点权的乘积，称做该结点的带权路径长度。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，称为树的带权路径长度，通常记为WPL： WPL=?wi×li i=1 n 其中：n为叶子结点的个数；wi为第i个叶子的权值； li为第i个叶子结点的路径长度。 结点的权：给树中每个结点赋予一个具有实际意义的数值，我们称该数值为这个结点的权。 * 例如下图所示的三棵二叉树 WPL(a)=7×2＋5×2＋2×2＋4×2＝36 其带权路径长度分别为： 2 4 5 7 a 7 5 4 b 2 5 4 2 c 7 WPL(b)=4×2＋7×3＋5×3＋2×1＝46 WPL(c)=7×1＋5×2＋2×3＋4×3＝35 * 什么样的树的带权路径长度WPL最小？ 例如：给定一个权值序列{2, 4, 5, 7}，可构造多种二叉树的形态: 问题： 2 4 5 7 a 7 5 4 b 2 5 4 2 c 7 WPL(a) ＝ 36 WPL(b) ＝ 46 WPL(c)＝35 其带权路径长度分别为： * 在各种形态的含有 n个叶子结点的 二 叉树中, 必存在一棵(几棵)其带权路径长度值WPL 最小的树，被称为“最优二叉树” 。 特征：在最优二叉树中没有度数为 1 的结点(可用反证法证明); 含 n个叶子结点的最优二叉树的总结点数为 2*n-1 (依据二叉树性质三)。 最优二叉树的构造方法最早由哈夫曼研究，所以又称为“哈夫曼树”。 * 二、如何构造最优树（哈夫曼算法） Step 1: 根据给定的 n 个权值 {w1, w2, …, wn}， 构造 一个具有n 棵二叉树的森林F = {T1, T2, … , Tn}， 其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树； Step 2:在 F 中选取其根结点的权值为最小和次小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和； Step 3: 从F中删去这两棵树,同时加入刚生成的新树； Step 4: 重复 2 和 3 两步,直至 F 中只含一棵树为止。 * 例如: 已知权值 W={ 5, 6, 2, 9, 7 } 9 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 构造哈夫曼树如下： 9 5 2 7 16 6 7 13 29 哈夫曼算法的实现 n个叶子结点的哈夫曼树共有2n-1个结点,因此可用有2n-1个元素的数组来存储哈夫曼树, 结点间的关系用游标表示，即采用静态链表来存储哈夫曼树。 1、存储结构 每个结点需包含其双亲结点信息和孩子结点信息，所以构成一个静态三叉链表。 weight parent Lchild Rchild 权值 双亲序号 左孩子序号 右孩子序号 * 静态三叉链表结构定义 #define N 20 #define M 2*N-1 typedef struct { int weight ; int parent，Lchild，Rchild ; }HTNode, HuffmanTree[M+1]; /*0号单元不用*/ 静态三叉链表数组中前 n 个元素存储叶子结点，后n-1个元素存储分支结点即不断生成的新结点，最后一个元素存储哈夫曼树的根结点。 * 2、哈夫曼算法 初始化：先将n个元素都视为根结点，即孩子和双亲指针全置0。 建哈夫曼树的过程是：反复在数组中选双亲为0(表示它们当前是树根)且权值最小的两结点, 将它们作为左右孩子挂在新的结点之下, 新结点权值为左右孩子权值之和。 * i i s2 i i s1 s1 s2 s1 s2 5 7 3 2 8 F: 2 3 5 5 7 8 15 10 5 10 15 25 25 1 2 3 4 5 6