在有N个叶子节点的哈夫曼树中，其节点总数为
在哈夫曼树（也叫最优树）中，只有两种类型的结点：度为0或N，即最优二叉树中只有度为0或2的结点，最优三叉树中只有度为0或3的结点，所以有2N-1个节点 。
给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
扩展资料：
哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。
解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)，则可以计算出其叶节点数目为(k-1)nk+1,式子中的nk表示子节点数目为k的节点数目。
于是对给定的n个权值构造k叉哈夫曼树时,可以先考虑增加一些权值为0的叶子节点，使得叶子节点总数为(k-1)nk+1这种形式,然后再按照哈夫曼树的方法进行构造即可。
参考资料来源：百度百科-哈夫曼树
在哈夫曼树（也叫最优树）中，只有两种类型的结点：度为0或n，即最优二叉树中只有度为0或2的结点，最优三叉树中只有度为0或3的结点，所以有2n-1个节点
。
在哈夫曼树（也叫最优树）中，只有两种类型的结点：度为0或N，即最优二叉树中只有度为0或2的结点，最优三叉树中只有度为0或3的结点，所以有2N-1个节点 。
霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。
树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明霍夫曼树的WPL是最小的。
扩展资料：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
参考资料：百度百科---哈夫曼树
在哈夫曼树（也叫最优树）中，只有两种类型的结点：度为0或N，即最优二叉树中只有度为0或2的结点，最优三叉树中只有度为0或3的结点，所以有2N-1个节点 。
如图
有2N-1个节点
根据定理，图中所有节点度数之和等于边的两倍。在树中，所有节点之和减一等于边数。
霍夫曼树为二叉树，只有三类节点，度为2的节点1个，度为3的节点x个，度为1的节点N个，所以:
2(1+x＋N)＝2×1＋x×3+N×1
解出x＝N－2;
所以总节点数＝x＋1+N＝2N－1
二叉哈夫曼，每个结点的度只能为0或者2，所以总得结点个数N=N0+N2=N0+N0-1=2n-1(这里叶子结点的个数等于度为二的结点个数加一，即N0=N2+1也就是N2=N0-1)
什么是哈夫曼树,它有哪些特点?
其次，哈夫曼树的特点在于它是一种最优二叉树。在最优二叉树中，树的每个节点的左右子树的选择都是为了使得整棵树的编码长度最小。哈夫曼树就是这种最优二叉树的一种特殊形式，它是由权值最小的n个叶子节点构造而成的。具体来说，哈夫曼树的构造过程如下：首先，将n个权值最小的叶子节点添加到一个...
...要求输入n=6,字母abcdef ,权值 分别是2,3,4,7,8,9.
void HuffmanCoding (HTNode ht[],HTCode hc[],int n ){ char cd[N];int i,j,m,c,f,s1,s2,start;m=2*n-1; \/\/有n个叶子节点的哈夫曼树有2n-1个节点 for(i=1;i<=m;i++){ if(i<=n) ht[i].weight=hc[i].weight;else ht[i].weight=0;ht[i].parent=ht[i].lchild=...
一个有n个结点的二叉树有多少个结点?
一共有2n-1个结点 设叶子节点个数为n，度为1的节点个数为m，度为2的节点个数为l.显然易知：一颗二叉树的节点数 ＝ 这个树的度加1（因为每个节点都是前一个节点的度，根节点除外，所以要加1）故有 l + m + n = 2l + m + 1---> n = l + 1由于哈夫曼树没有度为1的节点，在m ...
某二叉树中有n个叶子节点,则该二叉树中度为2的结点数为?
你好：这个一般都是填空题，答案：n+1 对任何一棵二叉树T,如果其终端节点数为n0,度为2的节点数为n2,则n0=n2+1.设n1为二叉树T中度为1的结点数.因为二叉树中所有结点的度军小于或等于2,所以其结点总数为 n=n0+n1+n2 (1)再看二叉树中的分支数.除了根结点外，其余结点都有一个分支进入，...
怎样构造哈夫曼树及其带权路径的求法
(2)在F中选取两颗根节点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根节点的权值为左右子树上根节点的权值之和。（3)在F中删除这两颗树，同时将新得到的二叉树加入F中。（4）重复（2）（3），直到F只含一棵树为止。这棵树就是哈弗曼树。如果有N个叶子节点，则哈弗曼树...
哈夫曼树的结点个数不能是偶数。
该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)，则可以计算出其叶节点数目为(k-1)nk+1,式子中的nk表示子节点数目为k的节点数目。
哈夫曼树的带权路径长度是多少?
由权值分别为3，8，6，2，5的叶子节点生成一棵哈夫曼树，它的带权路径长度为53。哈夫曼树满足对于n个带权节点，总可以用他们作为叶节点构造出一颗最小WPL值。树的带权路径长度记为WPL＝（W1＊L1＋W2＊L2＋W3＊L3＋...＋Wn＊Ln）。因为权值分别为3，8，6，2，5，所以WPL＝2＊3＋3＊3＋5...
若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为() 解析一...
但是与最优二叉树不同的是，给你的一组数据不一定恰好能构造出最优m叉树，原因是假设度为0的结点个数为x（也就是叶子结点），度为m的结点个数为y，则存在一个等式x+y=my+1，也就是说x-1能被m-1整除，但是给出你的数据个数（也就是x）不一定能整除啊，怎么办呢？第一，我们要计算(x-...
关于叶子节点有n个,求平衡二叉树的深度最多是多少
设根结点层次为1，则高度为h的平衡二叉树最少叶子结点个数就是Fibonacci数的F(h): 1,1,2,3,5,8,13,21,34,55,...看n在哪个Fibonacci数之间就可以了，当然，利用Fibonacci数的通项公式也可以求出，只是比较麻烦点
有N个节点的二叉树,其高度为多少
有N个节点的二叉树，其高度为Ω(logn)。高度为h≥0的二叉树至少有h+1个结点；高度不超过h(≥0)的二叉树至多有2h+1-1个结点；含有n≥1个结点的二叉树的高度至多为n-1；含有n≥1个结点的二叉树的高度至少为logn；因此其高度为Ω(logn)。
励肯悦康：[选项] A. 不确定 B. 2N-1 C. 2N+1 D. 2N
珠海市18710321236： 在有N个叶子节点的哈夫曼树中,其节点总数为()? - ？
励肯悦康： B
珠海市18710321236： 设哈夫曼树中共有n个结点,则该树中共有几个度数为1的结点 - ？
励肯悦康： (n+1)/2个叶子节点(度为1) 可以这样考虑,一开始只有一个叶子节点,每加入一个叶子节点,就增加一个度为2的节点,当叶子节点有k时,增加了k-1个度为2的节点n=2k-1;
珠海市18710321236： 哈夫曼树的总结点数与叶节点数的关系? - ？
励肯悦康： 由于哈夫曼树中没有度为1得结点. 只有度为0和度为2得结点. 则一棵有n个叶子结点得哈夫曼树共有2n-1个结点
珠海市18710321236： 具有m个叶结点的哈夫曼树共有多少个结点? - ？
励肯悦康： 因为哈夫曼树除了m个叶子结点就是二度结点,边数=结点个数-1=n0+n2-1 边的个数=2*n2,联立方程可知n2=n0-1,故n2=m-1,所以总结点个数为2m-1
珠海市18710321236： 哈夫曼树怎样构造编码? - ？
励肯悦康： 先编造哈夫曼树,哈夫曼树构造规则: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); (2) ...
珠海市18710321236： 哈夫曼树的构造,关键字如图 - ？
励肯悦康： 哈夫曼树构造规则:假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;(3)从森林中删除选取的两棵树,并将新树加入森林;(4)重复(2)、(3)步,直到森林中只剩一棵树为止 根据上述步骤得到的哈夫曼数是 (100) / \ (43) 57 / \ / \ (20) 23 (27) 30 / \ / \9 (11) 11 16 / \ 4 7
