递归树的高度与水平

Question

我读到树的高度为lgn，基数= 2，层数为lgn + 1。 b/w有什么不同？他们不包括高度计算中的最顶层还是基本情况？有人可以用一些实际的例子来证明我这个，用更多的语法来代替数学方程吗？

Answer 1

首先，高度为平衡的树是O（lg n）;完全不平衡的树（例如链表）的高度为O（n）。

节点的高度是它与根的距离（因此树的高度是从根开始的最大距离节点的任何节点）。从这个定义中，您可以看到根的高度为0，其子高度为1，，其子的子女的高度为2，依此类推。一个级别可以被认为是具有相同高度的所有节点。

现在考虑树中的一组等级。有0级的唯一方法是有一棵空树;只要有单个节点，就会有至少一个级别，即包含高度为0的根节点的级别。也就是说，在标签级别和级别之间存在差异，计数级别。 1级是高度为0的节点;等级2是具有高度1的节点的集合，等级i是具有高度i-1的节点的集合，直到达到由具有高度lg n的节点组成的等级lg n + 1。