Question

一棵二叉树一共有多少个结点？

Answer 1

一共有2n-1个结点

设叶子节点个数为n，度为1的节点个数为m，度为2的节点个数为l.
显然易知：一颗二叉树的节点数 ＝ 这个树的度加1（因为每个节点都是前一个节点的度，根节点除外，所以要加1）
故有 l + m + n = 2l + m + 1
----> n = l + 1
由于哈夫曼树没有度为1的节点，在m ＝ 0
总节点 ＝ n ＋ m ＋ l ＝ 2n － 1

扩展资料

在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

参考资料来源：百度百科-哈夫曼树