根据维基百科,
树的高度是从根到树中最深节点的路径的长度。只有一个节点(根)的(有根)树的高度为零(或一)。
我不明白 - 它是零还是一(或两者)?
根据维基百科,
树的高度是从根到树中最深节点的路径的长度。只有一个节点(根)的(有根)树的高度为零(或一)。
我不明白 - 它是零还是一(或两者)?
这只是您对二叉树高度的递归描述的假设。您可以考虑仅由高度为 0 或高度为 1 的节点组成的树。
如果你真的想以某种方式考虑它,你可以认为
这只是为了描述最小树的高度,然后在任何情况下,无论何时添加一个降序节点,您都会添加一个相关的边,因此它会相应地增加。
在维基百科提供的示例中:
这棵树的高度可以是 4(节点)或 3(边)。这取决于您是按边还是按节点计算它。
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.
取决于约定。这里没有“正确”的答案。我被教导它是 1。但零同样正确。
我认为,一个根节点的高度应该为 0。它具有实际意义,因为 2^height 也为您提供了该级别的节点数。
假设您在节点类中以递归方式计算高度,我会这样做以返回高度而不包括根的高度(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;
}
取决于您要如何解释树的高度。在某些应用程序中,具有一个节点的树被解释为高度为 1,而其他人则认为它的高度为零。