Обход дерева по порядку: какое определение является правильным?

Question

У меня есть следующий текст из академического курса, который я недавно изучал, о прохождении по порядку (они также называют это блин) из двоичного дерева (не BST):

Обход дерева обхода

Нарисуйте линию вокруг дерево. Начните слева от корня, и обойти снаружи дерева, в конечном итоге справа от корня. Оставайтесь как можно ближе к дереву, но не пересекать дерево. (Думать о дерево - его ветви и узлы - как твердый барьер.) Порядок узлы - это порядок, в котором эта строка проходит под ними. Если ты не уверены, когда вы идете «под» узел, помните, что узел «к слева »всегда на первом месте.

Вот пример (немного другое дерево снизу)

Однако, когда я выполняю поиск в Google, я получаю противоречивое определение. Например, пример Википедии :

Последовательность обхода в порядке: A, B, C, D, E, F, G, H, я (левый ребенок, корневой узел, правый узел)

Но согласно (моему пониманию) определению № 1, это должно быть

A, B, D, C, E, F, G, I, H

Может ли кто-нибудь уточнить, какое определение является правильным? Они оба могут описывать разные методы обхода, но могут использовать одно и то же имя. У меня проблемы с верой в то, что рецензируемый академический текст неверен, но не уверен.

Answer 1

В моей неудачной попытке рисования вот порядок, который показывает, как они должны быть выбраны.

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

Answer 2

Забудьте определения, гораздо проще применить алгоритм:

void inOrderPrint(Node root)
{
  if (root.left != null) inOrderPrint(root.left);
  print(root.name);
  if (root.right != null) inOrderPrint(root.right);
}

Это всего три строки. Изменить порядок заказа до и после заказа.

Answer 3

Если вы внимательно прочитаете, то увидите, что первое «определение» говорит о начале слева корня и что порядок узлов определяется тем, когда вы передаете в их. Таким образом, B не является первым узлом, так как вы передаете его слева на пути к A, затем сначала проходите в A, после чего вы идете вверх и проходите в B. Поэтому кажется, что оба определения дают один и тот же результат.

Answer 4

Я лично нашел эту лекцию весьма полезной.

Answer 5

Правильный обход будет: как можно левее с листовыми узлами (не корневыми узлами)

Left Root Right

A B NULL

C D E

Ноль F G

H I NULL

F - root или left, я не уверен

Answer 6

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

Answer 7

Я думаю, что первое двоичное дерево с корнем a является двоичным деревом, которое неправильно построено.

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

Answer 8

Оба определения дают одинаковый результат. Не дайте себя одурачить буквами в первом примере - посмотрите на числа вдоль пути. Во втором примере используются буквы для обозначения пути - возможно, это то, что сбивает вас с толку.

Например, в вашем примере, показывающем, как вы думали, что второе дерево будет пройдено с использованием алгоритма первого, вы ставите «D» после «B», но не должны, потому что есть еще левая рука Доступен дочерний узел D (поэтому первый элемент говорит «порядок, в котором эта строка проходит под ними».

Answer 9

void
inorder (NODE root)
{
  if (root != NULL)
    {
      inorder (root->llink);
      printf ("%d\t", root->info);
      inorder (root->rlink);
    }
}

Это самый простой подход к рекурсивному определению обхода по порядку, просто вызовите эту функцию в основной функции, чтобы получить обход по порядку для данного двоичного дерева.

Answer 10

Это верно для предварительного заказа, NT для заказа