单节点树高

Question

我在googled上搜索到，没有正确的答案，树高只有一个节点。有时是节点数，有时是边数，有时是1，而另一些时候是0。使用节点计数和其他时间边缘计数的情况是什么情况?

Answer 1

这完全取决于你对(1)树和(2)高度的定义。但是，我们当然希望保持一个属性，即高度是从树到整数的一个整体函数；不应该有未定义高度的树。

例如，假设我们有一个二叉树的定义：

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

type t = Empty | Node of t * t

现在我们可以定义高度，它应该是一个总函数:一棵空树的高度是零--它还能是什么？--非空树的高度是子树的高度加1：

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

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

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)) 

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

• 高度是一个整体函数。
• 一棵空树不是合法的树，而是一片叶子。
• 因此，叶子必须有高度。
• 一片叶子的合理高度是零。
• 因此，一棵单叶树的高度可以是零。

但是我们也可以说，叶子的高度是一个，如果不是这样定义的话，我们就会计算节点。从逻辑上说，这是没有异议的。

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

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

如果一个空树是不合法的，那么这两者都是合理的。由于这两个高度函数之间的关系是“它们完全不同”，所以使用哪个定义并不重要；如果要使用另一个定义，只需适当地添加或减去一个。

当平衡一棵树时，我们不关心绝对高度；我们关心两棵树之间的高度差异。在这些算法中，边和节点的计数都是不相关的。不管怎么说，差别都是一样的。很多时候这不重要，所以选择你更喜欢的哪一个。

Answer 2

节点的高度是从节点到叶子的最长路径上的边缘数，一个叶节点的高度为0。树高是根节点的高度。在您的情况下树的高度将是0。的详细答案，请检查这一个。What is the difference between tree depth and height?