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

给定 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）哈夫曼编码

（编辑：晋中站长网）

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