树，其中每个节点有两个孩子的节点的数量的节点

Question

我已经具有以下形式的树：

在第一张照片中，树的高度为1和有3个节点。 2为下一个7和3为15为最后一个。我怎样才能确定这种形式的树的高度将有多少个树节点？此外，什么样的树（特别是什么东西？）？

Answer 1

这是一个perfect binary tree

你可以考虑这个递归计算策略节点的数量：

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

所以

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

Answer 2

节点的一棵完整的树的数量..

n = 2 ^（h + 1） - 1.

Answer 3

深度'd'处的完整二叉树是严格二叉树，其中所有叶子都处于d级。

• 为FIG1，d = 1
• 为fig2，d = 2
• 为图三，d = 3

所以，假设深度d的二进制树T。然后在最

2(d+1)-1节点 n可以有在T.

• 为FIG1，d = 1; 2(1+1)-1 = 2(2)-1 = 4-1 = 3
• 对于图2，d = 2; 2(2+1)-1 = 2(3)-1 = 8-1 = 7
• 图3 d = 3; 2(3+1)-1 = 2(4)-1 = 16-1 = 15

的高度（h）和深度的树（从根部到叶节点的最长路径的长度）的（d）在数值上是相等的。

这是answer详细说明如何计算深度和高度。

Answer 4

您所描述的内容听起来像“完美的二叉树”。 “一棵二叉树是一棵树数据结构，其中每个节点至多有两个孩子” http://en.wikipedia.org/wiki/Binary_tree 一棵完美的树是“一棵二叉树，所有叶节点都在同一深度。“ http://xlinux.nist.gov/dads//HTML/perfectBinaryTree.html

高度完美的二进制树中的节点的最大数目 = 2 ^（高度+ 1）-1

数量的节点到最小高度 = CEILING（LOG（节点+ 1,2） -1,1）与二叉树相关

定义可以在前面提到的维基百科中找到。

Answer 5

这也可以被理解是这样的。

在完美二进制树的情况下 叶节点的总数为2 1 H（H =树的高度）

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

因此，如其他人所述，节点的总数将是2^H + 2^H-1，其为2 ^（H + 1）-1。

希望这会有所帮助。