30

根据维基百科,

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

我不明白 - 它是零还是一(或两者)?

4

6 回答 6

39

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

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

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

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

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

替代文字

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

于 2010-10-31T22:24:03.110 回答
14

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.

于 2010-10-31T23:21:52.543 回答
7

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

于 2010-10-31T22:22:32.283 回答
3

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

于 2013-09-23T14:05:28.807 回答
1

假设您在节点类中以递归方式计算高度,我会这样做以返回高度而不包括根的高度(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;
}
于 2018-06-26T06:51:32.887 回答
0

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

于 2010-10-31T22:25:10.690 回答