java - 在Java中查找二叉树中的最小键

Question

如何在二叉树中找到最小的键？如果它是二叉搜索树，则最小值将在最左侧，最大值将在最右侧(如果我没有理解错的话)，但二叉树没有这种顺序。

我似乎想不出什么好办法来解决这个问题。如果有人能帮忙那就太好了:)

Answer 1

这个问题可能最容易递归解决。

• 找到左子树的最小键。
• 您找到右子树的最小键。
• 将前两个元素相互比较并与当前节点的元素进行比较，然后返回 3 个元素中最小的一个。

这是一些伪代码:

KeyType getSmallestKey (Node root)
{
    minLeft = MAX_VALUE
    minRight = MAX_VALUE
    if root.hasLeftChild
        minLeft = getSmallestKey(root.left)
    if root.hasRightChild
        minRight = getSmallestKey(root.right)
    return min (minLeft, minRight, root.getKey)
}