最优二叉树
最优二叉树概念
．树的路径长度 树的路径长度是从树根到树中每一结点的路径长度之和 在结点数目相同的二叉树中 完全二叉树的路径长度最短
．树的带权路径长度(Weighted Path Length of Tree 简记为WPL) 结点的权 在一些应用中 赋予树中结点的一个有某种意义的实数 结点的带权路径长度 结点到树根之间的路径长度与该结点上权的乘积 树的带权路径长度(Weighted Path Length of Tree) 定义为树中所有叶结点的带权路径长度之和 通常记为 其中 n表示叶子结点的数目 w i和l i分别表示叶结点k i的权值和根到结点ki之间的路径长度 树的带权路径长度亦称为树的代价
．最优二叉树或哈夫曼树 在权为wl w … wn的n个叶子所构成的所有二叉树中 带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树 【例】给定 个叶子结点a b c和d 分别带权 和 构造如下图所示的三棵二叉树(还有许多棵) 它们的带权路径长度分别为 (a)WPL= * + * + * + * = (b)WPL= * + * + * + * = (c)WPL= * + * + * + * = 其中(c)树的WPL最小 可以验证 它就是哈夫曼树
注意 ① 叶子上的权值均相同时 完全二叉树一定是最优二叉树 否则完全二叉树不一定是最优二叉树 ② 最优二叉树中 权越大的叶子离根越近 ③ 最优二叉树的形态不唯一 WPL最小
构造最优二叉树
．哈夫曼算法 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法 故称其为哈夫曼算法 其基本思想是 ( )根据给定的n个权值w l w … wn构成n棵二叉树的森林F={T T … T n} 其中每棵二叉树T i中都只有一个权值为w i的根结点 其左右子树均空 ( )在森林F中选出两棵根结点权值最小的树(当这样的树不止两棵树时 可以从中任选两棵) 将这两棵树合并成一棵新树 为了保证新树仍是二叉树 需要增加一个新结点作为新树的根 并将所选的两棵树的根分别作为新根的左右孩子(谁左 谁右无关紧要) 将这两个孩子的权值之和作为新树根的权值 ( )对新的森林F重复( ) 直到森林F中只剩下一棵树为止 这棵树便是哈夫曼树 用哈夫曼算法构造哈夫曼树的过程见【动画演示】 注意 ① 初始森林中的n棵二叉树 每棵树有一个孤立的结点 它们既是根 又是叶子 ② n个叶子的哈夫曼树要经过n 次合并 产生n 个新结点 最终求得的哈夫曼树 *** 有 n 个结点 ③ 哈夫曼树是严格的二叉树 没有度数为 的分支结点 ．哈夫曼树的存储结构及哈夫曼算法的实现 （ ） 哈夫曼树的存储结构 用一个大小为 n 的向量来存储哈夫曼树中的结点 其存储结构为 #define n //叶子数目 #define m *n //树中结点总数 typedef struct { //结点类型 float weight //权值 不妨设权值均大于零 int lchild rchild parent //左右孩子及双亲指针 }HTNode typedef HTNode HuffmanTree[m] //HuffmanTree是向量类型 注意 因为C语言数组的下界为 故用 表示空指针 树中某结点的lchild rchild和parent不等于 时 它们分别是该结点的左 右孩子和双亲结点在向量中的下标 这里设置parent域有两个作用 其一是使查找某结点的双亲变得简单 其二是可通过判定parent的值是否为 来区分根与非根结点
（ ）哈夫曼算法的简要描述 在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree) ( )初始化 将T[ ．．m ]中 n 个结点里的三个指针均置为空(即置为 ) 权值置为 ( )输人 读人n个叶子的权值存于向量的前n个分量(即T[ ．．n ])中 它们是初始森林中n个孤立的根结点上的权值 ( )合并 对森林中的树共进行n 次合并 所产生的新结点依次放人向量T的第i个分量中(n≤i≤m ) 每次合并分两步 ①在当前森林T[ ．．i ]的所有结点中 选取权最小和次小的两个根结点[p ]和T[p ]作为合并对象 这里 ≤p p ≤i ② 将根为T[p ]和T[p ]的两棵树作为左右子树合并为一棵新的树 新树的根是新结点T[i] 具体操作 将T[p ]和T[p ]的parent置为i 将T[i]的lchild和rchild分别置为p 和p 新结点T[i]的权值置为T[p ]和T[p ]的权值之和 注意 合并后T[pl]和T[p ]在当前森林中已不再是根 因为它们的双亲指针均已指向了T[i] 所以下一次合并时不会被选中为合并对象 哈夫曼算法模拟演示过程【参见动画模拟】
（ ）哈夫曼算法的求精 void CreateHuffmanTree(HuffmanTree T) {//构造哈夫曼树 T[m ]为其根结点 int i p p InitHuffmanTree(T) //将T初始化 InputWeight(T) //输入叶子权值至T[ ．．n ]的weight域 for(i=n i<m i++){//共进行n 次合并 新结点依次存于T[i]中 SelectMin(T i &p &p ) //在T[ ．．i ]中选择两个权最小的根结点 其序号分别为p 和p T[p ] parent=T[p ] parent=i TIi] child=p //最小权的根结点是新结点的左孩子 T[j] rchild=p //次小权的根结点是新结点的右孩子 T[i] weight=T[p ] weight+T[p ] weight } // end for }上述算法中调用的三个函数【参见练习】 【例】以 个权值 为例 执行CreateHuffmanTree求最优二叉树的过程【参见动画模拟】
lishixinzhi/Article/program/sjjg/201311/23014
最优二叉树算法的基本概念
最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。那么什么是二叉树的带权路径长度呢？在前面我们介绍过路径和结点的路径长度的概念，而二叉树的路径长度则是指由根结点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值，...
哈夫曼树左小右大是指什么
最优二叉树的运算规则。哈夫曼树即为最优二叉树,其在进行计算时所使用的运算规则为左小右大,是求带权路径长度的运算方式。哈夫曼树是在叶子结点和权重确定的情况下,带权路径长度最小的二叉树。在计算机数据处理中，哈夫曼编码使用变长编码表对源符号进行编码，其中变长编码表是通过一种评估来源符号...
二叉树 两种存储结构的优缺点
一、顺序存储结构的优点：- 当需要读取或访问特定节点时，顺序存储结构具有较高的效率，时间复杂度为O(1)。顺序存储结构的缺点：- 在处理非完全二叉树时，会存在空间浪费的问题。二、链式存储结构的优点：- 相较于顺序存储，链式存储在访问特定节点时效率虽低，时间复杂度为O(n)，但在处理大规模二叉...
请教离散数学的二叉树和最优二叉树怎样定义
若根树的每个分至点至多有2个儿子，则称为二叉树。在所有入度为0的顶点（不一定是树叶）中选出两个权小的顶点，添加一个分支点，它以这2个顶点为儿子，其权等于这2个儿子的权之和。重复上述操作，直到只有1个入度为0的顶点为止。树是节点带权，之后乘上层数。一般的图权直接写在边上，是边带权...
最优二叉树
针对数据结构中的最优二叉树章节，做出笔记，以支持后期的回顾和了解。主要囊括了如下部分：二、讲解 1、哈弗曼 如图： 给定权值分别为 4、5、6、7 的A1、B1、C1、D1，可以构成几种或者多中的二叉树。2、如何构建最优二叉树 3、哈弗曼编码 首先我们将二叉树的左右分支分别定义为0、1。已知A...
哈夫曼树的带权路径长度为?
D 哈夫曼树：带权路径长度为 2*3 + 3*3 +5*2 +6*2 +8*2 = 53 如果是树的带权路径长度，就是树中所有叶子结点的带权路径长度之和。比如像赫夫曼树又称最优树，是一类带权路径长度最短的树。假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则...
哈夫曼树一定是完全二叉树吗
哈夫曼树不一定是完全二叉树。哈夫曼树是带权路径长度达到最小的二叉树，也叫做最优二叉树，不一定是完全二叉树，也不一定是平衡二叉树。哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素...
最优二叉树算法编码和解码
在上一章节中，我们已经了解了如何利用哈夫曼树创建字符编码方案。具体来说，当我们需要对数据文件进行编码时，首先需要遍历文件中的每个字符c，然后在已经构建好的哈夫曼编码表H中查找对应的编码。如果找到，即H[i].ch等于c，那么我们就可以将字符c替换为H[i].bits中存储的二进制编码序列。而在解码...
最优二叉树算法编码中的应用
例如，电文"ABACCDA"，用表3(a)编码后长度为21，但并非最优。另一种编码方案如表3(b)，采用等长编码，将电文编码为"00010010101100"，长度缩短至14。为了进一步压缩，编码应考虑字符频率，如表3(c)所示，"ABACCDA"的编码变为"0110010101110"，长度减至13。哈夫曼树是一种构建最优编码的有效工具。首...
最优二叉树怎么画
最优二叉树绘画步骤如下：1，构造森林全是根。这一步就是把这 n 个点放入结构体数组中：有 n 个点，每一个点用一次，共产生 n-1 个点，所以用到的数组长度为 2n-1。在实现的时候不用下标为 0 的位置，比较方便。2，选择两小造新树。就是在剩下没用过的点找到最小的两个数，即在那些...
魏佩白及： 最优二叉树,也称哈夫曼(Haffman)树,是指对于一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树.那么什么是二叉树的带权路径长度呢?在前面我们介绍过路径和结点的路径长度的概念,而二叉树的路径长度则是...
阳高县19799446214： 什么是带权最优二元树 - ？
魏佩白及：[答案] 一棵带权二元树的代价就是树中所有根结点权之和.代价最小的带权二元树称为最优二元树.问题转化为求最优带权二元树. 那么,什么是最优带权二元树呢? 最优二叉树,又称哈夫曼树,是一类带权路径长度最短的树,有着广泛的应用. 我们首先给出...
阳高县19799446214： 什么是最佳二叉树 - ？
魏佩白及： 最佳二叉树就是,就是最佳二叉查找树,即平均查找长度最短的二叉查找树.它的结点构成上的特点是:除了最下一层可以不满外,其他各层都是充满了的.
阳高县19799446214： 数据结构 最优二叉树 - ？
魏佩白及： 这是我们的作业题,自己写 的……(可能输入的格式跟你要的不一致,自己改一下) 如果有什么不懂的就问我,我可以把其中所有相关的文件发给你 ^^ 注:1、 初始化创建哈夫曼树有三种选择,其中选择编译课本测试数据时和编译源文件是,...
阳高县19799446214： 什么是最优二叉树?它的带权路径是如何表示的? - ？
魏佩白及： 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树.简单的认为就是叶子节点的值
阳高县19799446214： 如何构造最优2叉树 - ？
魏佩白及： 构造最优2叉树,就是找出最小的2个数,然后相加,重复直至最后一个数. 拿这道题来说,先找最小的2个数,即1和5,相加得6,现在最小的是6和6(有一个是计算出来的),相加得12,现在最小的是7和9,相加得16,然后12和16加起来得...
阳高县19799446214： 怎么求带权1,2,3,4,5,6,7,8,9,10的最优二叉树 - ？
魏佩白及：[答案] 1,2,3,4,5,6,7,8,9,10 1、先在序列里找权值两个最小的根结点.选1,2组成一棵二叉数. 然后,把1,2去掉.用根结点的权值3加入原序列.3,3,4,5,6,7,8,9,10 2、在新的序列中找权值两个最小的根结点.选3,3组成一棵二叉数. 然后,把3.3去掉.用根结点的权值6...
阳高县19799446214： 哈夫曼树问题 - ？
魏佩白及：[答案] 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree).
阳高县19799446214： 带权1,2,4,5,10,13的最优二叉树 - ？
魏佩白及： 最优二叉树,也就是赫夫曼树 是把带权值最小的两个数,相加得到它的双亲结点. 35 13 22 10 12 5 7 3 4 1 2
