Найти наименьший ключ в двоичном дереве в Java

Question

Как бы найти самый маленький ключ в двоичном дереве? Если это было двоичное дерево поиска, наименьшее значение было бы в крайнем левом углу, а самое большое - в крайнем правом (если я не понял), но двоичное дерево не имеет такого упорядочения.

Я, похоже, не думаю, что это хороший способ решить эту проблему. Было бы здорово, если бы кто-нибудь мог помочь :)

Answer 1

Эта проблема, вероятно, проще всего решить рекурсивно.

• Вы найдете самый маленький ключ левого поддерева.
• Вы найдете самый маленький ключ в правом поддереве.
• вы сравниваете прежние два элемента друг с другом и с элементом текущего узла и возвращаете самый маленький из трех элементов.

Вот некоторые псевдо-код:

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) 
}