【数据结构】4. 树与二叉树

在许多实际应用中，树中结点常常被賦予一个表示某种意义的数值，称为该结点的权。
从树根结点到任意结点的路径长度（经过的边数）与该结点上权值的乘积称为该结点的带权路径长度。
树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为
(WPL = sum_{i=1}^n w_itimes i_i)
式中，(w_i) 是第 i 个叶结点所带的权值；(i_i) 是该叶结点到根结点的路径长度。
在含有 N 个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称为最优二叉树。

例如，图 3-31 中的 3 棵二叉树，都有 4 个叶子结点 a、b、c、d，分别带权 7、5、2、4,它们的带权路径长度分别为

(a) WPL=7X2+5X2+2X2+4X2=36

(b) WPL=7X3+5X3+2X144X2=46

(c) WPL=7x]+5x2+2x3+4x3=35
其中图 4-31(c) 中树的 WPL 最小。可以验证，它恰为哈夫曼树。

（2）哈夫曼树的构造

给定 N 个权值分别为 (w_1,w_2,w_N) 的结点。
通过哈夫曼算法可以构造出最优二叉树，算法的描述如下：

1. 将这 N 个结点分别作为 N 棵仅含一个结点的二叉树，构成森林 F。
2. 构造一个新结点，并从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3. 从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中。
4. 重复步骤 2 和 3，直至 F 中只剩下一棵树为止。

从上述构造过程中可以看出哈夫曼树具有如下特点：

1. 每个初始结点最终都成为叶结点，并且权值越小的结点到根结点的路径长度越大。
2. 构造过程中共新建了 N-1 个结点（双分支结点），因此哈夫曼树中结点总数为 2N-1。
3. 每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点。

例如，权值{7,4}的哈夫曼树的构造过程如图 4-32 所示。

（3）哈夫曼编码

（编辑：浙我家）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!