一棵每个节点都有两个子节点的树的节点数量

Question

我有一棵树，它的形态如下：

在第一张图片中，树的高度为1，总共有3个节点。在下一张图中，7有2个节点，15有3个节点。我该如何确定这种高度为l的树将有多少个节点？此外，这是什么样的树（有没有特定的称呼）？

- Oti Na Nai

---

这是一棵完全二叉树吗？ - zhangyiying

它既是一个完全二叉树，也是一个满二叉树...这使它成为一个完美的二叉树（请参见我回答中的维基百科链接）。 - Amxx

Answer 1

这是一个 完美二叉树

你可以使用递归方法计算节点数：

n(0) = 1
n(l+1) = n(l) + 2^l

所以

n(l) = 2^(l+1) - 1

- Amxx

Answer 2

深度为'd'的完全二叉树是一棵严格的二叉树，其中所有叶子节点都在第d层。

• 对于fig1，d=1
• 对于fig2，d=2
• 对于fig3，d=3

因此，假设有深度为d的二叉树T。则T中最多可以有

2(d+1)-1

个节点n。

• 对于fig1，d=1; 2(1+1)-1=2(2)-1=4-1=3
• 对于fig2，d=2; 2(2+1)-1=2(3)-1=8-1=7
• 对于fig3，d=3; 2(3+1)-1=2(4)-1=16-1=15

树的高度(h)和深度(d)（从根到叶节点的最长路径长度）相等。

这里有一个答案详细说明如何计算深度和高度。

- Ashesh

---

注意：因为错误地混淆了上标的HTML标记，导致投票下降。已经纠正了错误的等式。 - Ashesh

Answer 3

完全二叉树的节点数为…

n = 2^(h+1) - 1.

- ChiefTwoPencils

Answer 4

您所描述的听起来像是"完美二叉树"。 "二叉树是一种树形数据结构，其中每个节点最多有两个子节点" http://en.wikipedia.org/wiki/Binary_tree 完美二叉树是指 "所有叶子节点深度相同的二叉树。" http://xlinux.nist.gov/dads//HTML/perfectBinaryTree.html 完美二叉树高度到最大节点数的关系为 =2^(height+1)-1

节点数到最小高度的关系为 =CEILING(LOG(nodes+1,2)-1,1)

有关二叉树的定义可以在前面提到的维基百科中找到。

- Bryan Ritter

Answer 5

这也可以这样理解。

对于一个完美的二叉树，叶节点的总数为2^H（其中H为树的高度）

内部节点的总数为2^H - 1

因此，节点的总数将是2^H + 2^H - 1，即其他人提到的2^(H+1) - 1。

希望这能帮到你。

- V Chauhan