Двойной порядок обхода двоичного дерева

Question

Может кто-нибудь объяснить мне прохождение двойного порядка?

        A
      /   \
     B     E
   /  \   /  \
  C   D  F    G

Вывод двойного ордера: ABCCBDDAEFFEGG

Меня интересует объяснение, а не код.

Спасибо

Answer 1

Предполагая, что вас интересует объяснение того, что делает обход двойного порядка:

Для каждого обхода вы

• Посетите узел
• Пройдите влевоРебенок
• Посетите узел
• Пройдите через Правый ребенок

Это все, что нужно сделать.В тех случаях, когда у вас нет левого потомка (например, C), две операции «посещение узла» происходят вплотную, поэтому вы видите два C в своих выходных данных.

Просто длявизуализируйте его (с выделением жирным шрифтом):

• Визит A: A
• Перемещение левого потомка B
• • Визит B: AB
• • Траверса левого ребенка C
• • • Визит C: ABC
• • • Нет оставленного ребенка
• • • Визит C: ABCC
• • • Нет правого ребенка
• • Пройдите правого ребенкаD
• • • Визит D: ABCCD
• • • Не осталось ребенка
• • • Визит D: ABCCDD
• • • Нет правильного ребенка
• Визит A: ABCCDDA
• Траверса правого ребенка E
• • Посетите E: ABCCDDAE

и т. Д.

Answer 2

В основном это рекурсивный подход для обхода дерева (здесь мы имеем дело с двоичным деревом)

Вот алгоритм обхода двойного порядка:

Алгоритм DoubleOrder (root))

1. if (корень не NULL)

   1. print (корень)
   2. DoubleOrder (leftSubtree) // рекурсивный вызов
   3. print (root)
   4. DoubleOrder (rightSubtree) // рекурсивный вызов

2. endif

3. end DoubleOrder

Объяснение:

1. Посетите A и распечатайте Вывод: A
2. A оставили поддерево
   1. Посетите B и распечатайте Вывод: AB
   2. B осталось левое поддерево
      1. зайти в C и распечатать его вывод: ABC
      2. C не имеет левого поддерева
      3. Снова зайти в C и распечатать его вывод: ABCC
      4. C не имеет поддерева
      5. возврат в B (все 4 утверждениявыполнили в случае C)
   3. Посетите B снова и напечатайте его вывод: ABCCB
   4. B имеют правильное поддерево
      1. посетите D и распечатайте его Вывод: ABCCBD
      2. D не имеет левого поддерева
      3. Посетите D еще раз и распечатайте его Вывод: ABCCBDD
      4. D не имеют поддерева
      5. возврат в B (все 4 оператора выполнены в случае D)
   5. возврат в A (все 4 оператора были выполнены в случаеB)
3. Снова посетите A и распечатайте его Вывод: ABCCBDDA
4. A имеют правильное поддерево
   1. Посетите E и распечатайте его вывод: ABCCBDDAE
   2. E покинул поддерево
      1. посетить F и распечатать его вывод: ABCCBDDAEF
      2. F не имеет левого поддерева
      3. Снова посетите F и распечатайте его output: ABCCBDDAEFF
      4. F не имеют поддерева
      5. возврат к E (все 4 оператора были выполнены в случае F)
   3. Посетите E еще раз и напечатайте его вывод: ABCCBDDAEFFE
   4. E имеют правильное поддерево
      1. посетите G и распечатайте его вывод: ABCCBDDAEFFEG
      2. G не имеет левого поддерева
      3. Посетите G снова и напечатайте его Вывод: ABCCBDDAEFFEGG
      4. G не имеет поддерева
      5. возврат к E (все 4операторы выполнились в случае G)
   5. возврат к A (все 4 оператора выполнились в случае E)
5. Остановите выполнение, каквернуться к основному корню дерева (так как все 4 оператора были выполнены в случае A)

Окончательный вывод: ABCCBDDAEFFEGG

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

Answer 3

Рекурсировать через:

1. Visit root of (sub)tree.
2. Visit left subtree.
3. Revisit root of (sub)tree.
4. Visit right subtree.

Случайно, я не могу придумать приложение для него, хотя я сделал несколько действительно странных вещей с кучей узлов, которые находятся в нескольких деревьях (и связанных списках) одновременно.

Answer 4

Представьте, что вы идете, начиная с корня.

1. Вы находитесь на A;
2. Идите к левому ребенку, вы попадаете в B;
3. Прогулка к левому ребенку, C;
4. Тупик, ты поворачиваешь назад, все еще C;
5. Назад в B;
6. Подойдите к правому ребенку, к D;
7. Тупик, поверните назад, неподвижно D;

и т.д.

Это просто обход такого рода как в, так и в обратном направлении.

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