单节点树的高度

Question

我用谷歌搜索了一下，只有一个节点的树高度没有正确的答案。有时是节点数，有时是边数，导致有时为 1，有时为 0。使用节点计数和其他时间使用边缘计数的情况是什么？

Answer 1

这完全取决于您对 (1) 树和 (2) 高度的定义。但我们当然希望保持这样的性质：高度是从树到树的总函数；不应该有未定义高度的树。

假设我们有这样的二叉树定义：

树被定义为 (1) 空树，或 (2) 一对树，称为左子树和右子树。

type t = Empty | Node of t * t

现在我们可以定义高度，它应该是一个全函数：一棵空树的高度为零——它还能是什么呢？-- 非空树的高度是子树高度中较大者加一：

let max x y = if x > y then x else y
let rec height tree = match tree with 
  | Empty -> 0
  | Node (left, right) -> 1 + max (height left) (height right)

现在，请注意我们到达这里的逻辑链：

• 高度是一个总函数
• 空是合法树
• 因此一棵空树必须有一个高度
• 空树唯一合理的高度为零
• 因此，具有单个节点的树的高度必须为 1。

如果我们否认其中一些前提，那么我们可以得出其他答案。例如，如果没有空树怎么办？

树被定义为树的列表，可能是空的：

type t = Node of t list

我们可以再次给出高度的定义：具有空列表的节点的高度定义为零，具有非空子节点的节点的高度是最大子节点高度加一。

let max x y = if x > y then x else y
let rec height tree = match tree with
  | Node [] -> 0
  | Node h :: t -> max (1 + height h) (height (Node t)) 

在这个定义中，具有单个节点的树的高度为零，并且我们正在计算边。再次看看我们的推理：

• 高度是一个总函数
• 一棵空树不是一棵合法的树，但一片叶子是
• 因此叶子必须有一个高度
• 叶子的合理高度为零
• 因此，单叶树的高度可能为零。

但我们也可以说叶子的高度是 1，否则具有相同的定义，并且我们将计算节点。从逻辑上讲，没有人反对这一点。

使用节点计数和其他时间使用边缘计数的情况是什么？

如果空树是合法的，那么显然只有节点数才有意义。如果我们尝试计算边数，则无法区分空树的高度和单节点树的高度，并且将高度保持为总函数。

如果空树不合法，那么两者都有意义。由于两个高度函数之间的关系是“它们相差一倍”，因此使用哪种定义并不重要；如果您想使用其他定义，只需适当添加或减去一个即可。

当平衡一棵树时，我们不关心绝对高度；我们关心的是树的绝对高度。我们关心两棵树之间的高度差异。在这些算法中，我们计算边还是节点是无关紧要的。无论如何，差异将是相同的。很多时候这并不重要，所以选择你更喜欢的。