我正在阅读算法设计手册。作者指出树的高度是：
h = log n,
where
h is height
n = number of leaf nodes
log is log to base d, where d is the maximum number of children allowed per node.
然后他继续说完美平衡的二叉搜索树的高度将是：
h = log n
我想知道n第二个语句中是否表示“叶节点总数”或“节点总数”。
这就提出了一个更大的问题，节点总数与完美平衡的二叉搜索树的高度之间是否存在数学关系？
当然，n = 2^h其中h, n分别表示树的高度和它的节点数。
证明草图：
一棵完全平衡的二叉树有
关于完美平衡二叉树中的叶节点：
由于叶子数是节点数减去高度减一的完全平衡二叉树中的节点数，因此叶子数是所有节点数的一半（准确地说，是 的一半n+1）。
所以h只是变化 1，这通常不会对复杂性考虑产生任何真正的影响。可以通过记住它与将单个节点树的高度定义为 0（标准）或 1（不寻常，但可能有助于将其与空树区分开来）来说明这种说法。
如果您谈论所有节点或仅谈论叶节点，这并不重要：其中一个受上下约束，另一个乘以一个常数因子。在完全平衡的二叉树中，全层的节点数是上一层的所有节点数加一。
在完整的二叉树中，节点数 (n) 和树的高度 (h) 具有如下关系。
n = 2^(h+1) -1
这是树的所有节点