как найти следующий больший ключ бинарного дерева поиска в др. ракетка?

Question

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

Обновление:

    10
   /  \
  6   11
   \
    8

В этом бинарном дереве, учитывая 10, мне нужно найти следующее более высокое, 11. Принимая 8, мне нужно найти 10, но я не знаю, как вернуться назад, потому что моя рекурсия обновляет всю мою предыдущую информацию.

Спасибо !

Answer 1

Итак, у вас есть проблемы с тем, что вы посетили самый высокий и прошли второй по величине и не знаете, как go вернуться?

  5
 /  \
1   10

Но вы знаете, что делать в этом ситуация?

   5
 /  \
1   10
   /  \
  7    12

Хотя это точно так же, как узел 5 не проблема, создание важного дерева:

  10
 /  \
7   12

Я предполагаю, что настоящая проблема заключается в когда у вас есть это дерево без родителей:

  10
 /
7

Или, что еще хуже, у вас есть это, когда у вас действительно нет ответа:

10

Я полагаю, вы сохраните 2 узла:

(define (find-second-biggest-helper parent node)
  (if (not (tree-null? (right node)))
      (find-second-biggest-helper node (right node)
      ...))