20

我似乎无法为此找到明确的答案，我正在尝试对堆做一些基本的证明，但这就是让我有点失望的原因：

一棵空树有效吗？如果有，它的高度是多少？
我认为这将是0。

具有单个节点的树的高度是多少？
我认为这将是 1，但我已经看到它是 0 的定义（如果是这种情况，那么我不知道如何解释一棵空树）。

4

7 回答 7

23

树的高度是从树的根到其最远节点（即离根最远的叶节点）的路径长度。

仅具有根节点的树的高度为 0，而具有零节点的树将被视为空。一棵空树的高度为-1。请检查这个。

我希望这有帮助。

于 2010-02-05T19:28:47.317 回答
9

我认为你应该看看NIST 网站上的算法和数据结构词典。高度的定义表示单个节点的高度为 0。

有效树的定义确实包含一个空结构。该网站没有提到这种树的高度，但根据高度的定义，它也应该是 0。

于 2010-02-05T19:34:11.413 回答
5

我已经看到它以两种方式使用（将单个节点计为 0 或 1），但大多数来源会将仅根树定义为高度为 0 的树，并且不会认为 0 节点树有效。

于 2010-02-05T19:30:53.910 回答
2

如果你的树是一个递归定义的数据结构，它可能是空的，也可能是一个带有左右子树的节点（例如搜索树或你的堆），那么自然定义是将 0 分配给空树，并将 1 +最高子树到非空树的高度。

如果你的树是一个图，那么自然定义是从根到叶子的最长路径，所以只有根的树的深度为 0。在这种情况下，你通常甚至不会考虑空树。

于 2010-02-05T19:53:58.357 回答
2

树的高度是其任一子节点中到终端节点的最长路径的长度。

维基百科说一棵空树的高度是 -1。我不同意。一棵空树实际上只是一棵包含一个终端节点的树（一个空值或表示一棵空树的特殊值）。由于该节点没有子节点，因此其最长路径的长度必须是空和= 0，而不是 -1。

同样，一棵非空树有两个孩子，因此根据定义，至少有一条 >= 1 的路径到终端节点。

我们可以如下定义我们的树：

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

let rec height = function
    | Node(left, x, right) -> 1 + max (height left) (height right)
    | Nil -> 0
于 2010-02-05T20:09:16.410 回答
0

根据Wikipedia，具有单个节点的（子）树的高度为 0。没有节点的树的高度为 -1。但我认为这取决于你，你如何定义高度，你的证明应该适用于任何一个定义。

于 2010-02-05T19:31:56.453 回答
-5

实际上，树高度的完美定义是从根开始的 d 最长路径的叶子的 d 级别加上 1..accordin 2 这个定义的 fa 树是空的，它不会有任何级别 nv 不能认为它为零，因为根的级别s 零 ..so 空树级别是 -1，比accordin 2 defn 它的 -1+1=0 ..so 零 sd 空树的高度...bt n 他们给出了很多书 -1 bt 没有给出解释

于 2010-10-20T12:53:21.117 回答