tree - 非二叉树的高度是对数吗？

Question

如果我有一棵树，每个节点可以有可变数量的子节点，那么树的高度是对数的吗？

例如，在 n 个元素的二叉树中，高度为 log(n)。

Answer 1

Mushfiqur 是正确的——非二叉树的高度可能从 log(n) 到 n 变化。如果每个节点只有一个子节点，则高度为n。这样的树实际上看起来像一个单链表数据结构。

另一方面，在除叶节点之外的每个节点都有其最大子节点数，并且每个子树都等高(或等高 1)的情况下，我们有一个平衡树。只要一棵树是平衡的，它的高度就永远是log(n)。

请记住，log(n)并不总是log(n)!当我们谈论计算机科学时，我们通常谈论log2(n)，但是当谈论m'二叉树时，我们必须使用log m( n) 获取实际高度。例如。每个节点都有三个子节点的平衡树的高度为 log3(n)。