每个节点有两个子节点的树的节点数

Number of nodes of a tree where each node has two children nodes

我有一个具有以下形式的树：

在第一张图片上，树的高度为1，总共有3个节点。 2 下一个 7 和 3 15 最后一个。如何确定这种形式 l 高度的树将具有多少个节点？还有，那是什么树（有什么特别的名字吗？）？

那是一个perfect binary tree

你可以通过递归的方式得到节点数：

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

所以

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

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

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

深度为“d”的完全二叉树是严格的二叉树，其中所有叶子都在级别 d。

  • 对于图 1，d=1
  • 对于图 2，d=2
  • 对于图 3，d=3

所以，假设一棵深度为d的二叉树T。那么最多

2<sup>(d+1)</sup>-1

节点 n 可以存在于 T.

  • 对于图 1，d=1； 2<sup>(1+1)</sup>-1=2<sup>(2)</sup>-1 =4-1=3
  • 对于图 2，d=2； 2<sup>(2+1)</sup>-1=2<sup>(3)</sup>-1 =8-1=7
  • 对于图 3 d=3； 2<sup>(3+1)</sup>-1=2<sup>(4)</sup>-1 =16-1=15

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

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

您的描述听起来像 "a perfect binary tree"。 "a binary tree is a tree data structure in which each node has at most two children" http://en.wikipedia.org/wiki/Binary_tree 一棵完美的树是 "A binary tree with all leaf nodes at the same depth." http://xlinux.nist.gov/dads//HTML/perfectBinaryTree.html

完全二叉树中最大节点数的高度 =2^(身高+1)-1

最小高度的节点数 =天花板（日志（节点+1,2）-1,1）

与二叉树相关的定义可以在前面引用的维基百科 wiki 中找到。

这个也可以这样理解。

如果是完美二叉树 叶节点总数为 2^H (H = 树的高度)

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

因此节点总数将为 2^H + 2^H - 1 即 2^(H+1) - 1 正如其他人提到的那样。

希望这会有所帮助。