Удаление двоичного дерева - PullRequest
Новая
       6

Удаление двоичного дерева

2 голосов
/ 06 ноября 2011

У меня есть двоичное дерево и обход по предварительному заказу.Вот мое дерево.

      15
     / \
   10   23
   /\   /\
  5 12 20 30
    /     /
   11    25
          \
          27

итак результат предварительного заказа: 15 10 5 12 11 23 20 30 25 27. Все нормально

Чем я удаляю 5,12 и 23 элемента

Должен ли я получить это 

          15
         / \
       10   27
        \   /\
        11 20 30
               \
               25

Результат: 15 10 11 27 20 30 25

или это? 

      15
     / \
   10   25
    \   /\
    11 20 30
          /
         27

Результат: 15 10 11 25 20 30 27

PS У меня второй случай.Если это не правильно, что не так с удалением?

UPD: ТАК, второй обновленный вариант прав?

Ответы [ 2 ]

1 голос
/ 06 ноября 2011

Ваш второй случай почти прав. 27 будет левым узлом 30. При удалении верхнего узла (под) дерева вы можете либо заменить этот узел самым правым узлом левой ветви, либо самым левым узлом правой ветви. В этом случае вы заменили 30 на крайнее левое значение правой ветви, которое равно 25. Вы должны выполнить это рекурсивно, так как 25 имеет свои собственные ветви. Как только ваш целевой узел для удаления станет листом, удалите его.

Первый шаг: 

      15
     / \
   10   25
    \   /\
    11 20 30
          /
         23
          \
           27

Второй шаг: 

      15
     / \
   10   25
    \   /\
    11 20 30
          /
         27
        / 
       23

Третий (удаление): 

      15
     / \
   10   25
    \   /\
    11 20 30
          /
         27
0 голосов
/ 06 ноября 2011

Если вы хотите, чтобы обход по предварительному заказу оставшихся элементов был совместим с обходом по предварительному заказу до удаления, то ваше дерево должно выглядеть так: 

   15
  / \
10   20
 \    \
 11    30
       /
      25
       \
        27

Метод удаления:

Если есть левое поддерево удаленного узла, переместите корень левого поддерева в удаленную позицию. Перейдите по ссылкам правого поддерева в (ранее) левом поддереве и прикрепите правое поддерево к первой пустой правой ссылке. Если левого поддерева нет, переместите корень правого поддерева в удаленную позицию.

...