本文共 685 字,大约阅读时间需要 2 分钟。
1、哈夫曼树,又叫最优二叉树:效率最高的判决数。
2、回忆树的相关知识
① 路径长度:路径上的结点数 - 1。
② 结点的权:在许多应用中,常常给树的结点赋予一个有意义的数,称为该结点的权。
③ 结点的带权路径长度:该结点到树根的路径长度 × 该结点的权。
④ 树的带权路径长度:树上所有叶子结点的带权路径长度之和,通常记作 WPL 。
3、哈夫曼树定义
在权为w1, w2, …, wn的 n 个叶子结点的所有二叉树中,带权路径长度 WPL 最小的二叉树称为赫夫曼树或最优二叉树。
4、哈夫曼树的构造(哈夫曼算法)
① 根据给定的 n 个权值 { w1, w2, … , wn } 构成二叉树集合 F = { T1, T2, … , Tn },其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点,其左右子树为空。
② 在 F 中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和。
③ 在 F 中删除这两棵树,同时将新的二叉树加入 F 中。
④ 重复2、3,直到 F 只含有一棵树为止。(得到哈夫曼树)
5、关于哈夫曼树的注意点
① 满二叉树不一定是哈夫曼树;
② 哈夫曼树中权越大的叶子离根越近(很好理解,WPL最小的二叉树);
③ 具有相同带权结点的哈夫曼树不惟一;
④ 哈夫曼树的结点的度数为 0 或 2, 没有度为 1 的结点;
⑥ 包含 n 个叶子结点的哈夫曼树中共有 2n – 1 个结点;
⑦ 包含 n 棵树的森林要经过 n–1 次合并才能形成哈夫曼树,共产生 n–1 个新结点。
参考:
转载地址:http://fxtai.baihongyu.com/