java - 二 fork 树的最左节点和最右节点是什么？

Question

我正在阅读this在一个地方写着

最右边的节点将是左子树中具有最大值的节点，我假设最左边的节点是右子树中的最大值。

但是，在 another article它向我展示了查找最左边节点的不同方法:

1) 如果给定节点没有右子节点:

转到给定节点的根，直到它是任何节点的左子节点。该节点将是树中的下一个更高节点。

2) 如果给定节点有右子节点:

a) 如果给定节点的右子节点没有左子节点

The right child will be the next higher node.

b) 如果给定节点的右子节点有左子节点

The leftmost leaf node will be the next higher node.

即第二种方法不会像第一种方法建议的那样返回最大值(value)，请澄清..

Answer 1

根据您附加的链接判断，我假设您专门讨论二叉搜索树，它具有有关其节点构成的规则。

作为二叉树(以及扩展的子树)的一般规则:

• 节点右侧的每个子节点都将大于该节点。
• 节点左侧的每个子节点都小于该节点。

因此，任何给定子树的最右边的子节点将始终是最高值。此外，任何给定子树的最左边的子节点始终是最低值。

请记住，二叉树与二叉搜索树略有不同，这些规则不一定适用于二叉树。

让我们使用以下二叉搜索树作为示例:

        9
      /   \
     4     13
   /  \   /  \
  1   5  11  16

假设我们正在尝试寻找树中的最高节点值。 如果我们从节点 9(“根”)开始，我们将继续向下遍历该节点的每个右子节点，直到不再有右子节点(即从节点 9 开始，然后向下移动到节点 13，然后结束节点 16 )。因此，16 是树中的最高值。

与搜索树中的最低节点值类似，我们从树的根节点开始，继续向下遍历每个左子节点，直到不再存在左子节点。

来源:在大学的数据结构和算法类(class)中学到了这一点(IT 学生)

希望这对您有所帮助，并且请随时纠正我可能犯的任何错误(我是新来的)。