大家看看这道题：数据结构：试证明：有n（n>1）个权值所构造的HUFFMAN树中不存在度为1的节点。

分真不多了，就十分，大家帮帮忙，看看怎么证明？

推荐答案 2013-12-13

赫夫曼树即为最优树，其定义为带权路径长度最短的树。当N>1时，可以假设存在度为1的节点，即该节点有一个子树。设该节点为A，其子节点为B。可将AB合并为一个节点，则B以下的叶子结点的路径长度减小，树的带权路径长度减小。显然合并后的树其带权路径长度之和小于原树，与原树是赫夫曼树的已知条件相悖。故假设是不成立的。得证。

温馨提示：答案为网友推荐，仅供参考

当前网址：http://77.wendadaohang.com/zd/WY8qI83qppNNpGN3GY.html

其他回答

第1个回答 2017-08-22

反证法：若存在度为1的节点，那么该节点有一个子树。设该节点为A，子节点为B。因为A是由B与另一个节点相加而得，而现在只有一个节点，那么A=B。将AB合并为一个节点，则B以下的叶子结点路径长度减少，树的带权路径长度减少，合并后其带权路径之和小于原树，而哈夫曼树已经是带权路径长度最短的树，所以与原树是哈夫曼树相悖，所以假设不成立。本回答被网友采纳

相似回答

到底什么是哈夫曼树啊,求例子答：哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。例子：1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；2...

求助有关哈夫曼树的问题!急!满意的答案再加!答：可以证明最后一棵二叉树是哈夫曼树。二、构造哈夫曼树 1. 将n个叶结点构成独立的n棵二叉树，每棵二叉树只有一个根结点。2. 选择两棵权值最小的二叉树合并成一棵二叉树，并以这两棵二叉树的权值之和作为这棵二叉树的权值，取消原来的两棵二叉树。3. 重复2，知道只剩一棵二叉树为止。例如：有...

九、数据结构-非线-树答：带权路径长度最小的树。核心思想：使权大的结点靠近根。性质：一棵有n个叶子结点的Huffman树有2n-1个结点。因为从哈夫曼树形成来看，初始结点最终一定在叶子的位置，上面都是新增的结点，4个结点的哈夫曼树最终一定新增三个结点。构造过程：哈夫曼树的构建：说明1： SelectNode()有两...

{4,5,6,7,8}作为权值构造Huffman树,带权路径长度?答：先是4和5合并为9，再就是6和7合并为13，接着是8和9合并为17，最后是13和17合并为30，所以WPL = (6+7+8)*2 + (4+ 5)*3= 69。例如：假设有n个权值，则构造出的哈夫曼树有n个叶子结点，n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：(1) 将w1、w2、…，wn看成是...

谁有关于二级c公共基础知识的东西,发一个给我答：算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本基本概念数据结构研究的三个方面:(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的...

数据结构的问题~答：A n(n-1)/2 B n2/2 C n(n-1)/2 D n 二、简答题 1 数据的逻辑结构有哪几种?常用的存储有哪几种? 2 举一个数据结构的例子,叙述其逻辑结构、存储结构和运算三方面的内容。 3 什么叫算法?它有哪些特性 4 有下列几种用二元组表示的数据结构,画出它们分别对应的逻辑结构图,并指出它们分别以属于何种...

某校六年级学生共有367人,年龄最大的与年龄最小的相差不到1岁,我们...答：这是抽屉原理的题目因为一年最多有366天(闰年)最多只有366个人生日不一样现在班上有367个人,所以至少有两个人生日相同附:抽屉原理:第一抽屉原理原理1 把多于n个的物体放到n个抽屉里,则至少有一个抽屉里有2个或2个以上的物体。抽屉原理[证明](反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多...

大家正在搜

如何证明一个数据结构是线程安全的数据结构证明题汇总数据结构性质二证明数据结构编程题数据结构问答题数据结构怎么考试数据结构综合题数据结构算法设计题数据结构经典例题