tree - 只有一个节点的树的高度

Question

根据维基百科，

树的高度是从根到树中最深节点的路径的长度。只有一个节点（根）的（有根）树的高度为零（或一）。

我不明白 - 它是零还是一（或两者）？

Answer 1

这只是您对二叉树高度的递归描述的假设。您可以考虑仅由高度为 0 或高度为 1 的节点组成的树。

如果你真的想以某种方式考虑它，你可以认为

• 如果您将高度视为边数，则为 0（因此单个节点没有任何边，因此为 0）
• 如果您将高度视为节点数，则为 1（因此单个节点计为 1）

这只是为了描述最小树的高度，然后在任何情况下，无论何时添加一个降序节点，您都会添加一个相关的边，因此它会相应地增加。

在维基百科提供的示例中：

这棵树的高度可以是 4（节点）或 3（边）。这取决于您是按边还是按节点计算它。

Answer 2

One advantage of using a node count rather than an edge count is that it distinguishes the empty case (zero nodes, and node level) from the minimal case (one node, and a node level of one). In some cases, an empty tree will not be meaningful, but in other cases an empty try will be perfectly legitimate.

Answer 3

取决于约定。这里没有“正确”的答案。我被教导它是 1。但零同样正确。

Answer 4

我认为，一个根节点的高度应该为 0。它具有实际意义，因为 2^height 也为您提供了该级别的节点数。

Answer 5

假设您在节点类中以递归方式计算高度，我会这样做以返回高度而不包括根的高度（java代码）：

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height() + 1;
    if(right != null)
        rightHeight =+ right.height() + 1;
    return Math.max(leftHeight, rightHeight);
}

如果你想包括根的高度，那么我会这样做：

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height();
    if(right != null)
        rightHeight =+ right.height();
    return Math.max(leftHeight, rightHeight) + 1;
}

Answer 6

取决于您要如何解释树的高度。在某些应用程序中，具有一个节点的树被解释为高度为 1，而其他人则认为它的高度为零。