Обход дерева Inorder: Какое определение корректно?

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

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

, К сожалению, Ваше понимание является неправильным.

Каждый раз, когда Вы прибываете в узел, необходимо убывать к доступному левому узлу перед рассмотрением текущего узла затем Вы смотрите на доступный правильный узел. При выборе D прежде C Вы не убывали к левому узлу сначала.

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

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

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

Забудьте определения, настолько легче просто применить алгоритм:

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

Это - всего три строки. Перестройте порядок на пред - и пост - порядок.

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

До A, B, C, D, E, F, я думаю, вы уже поняли. Теперь после корня F следующим узлом будет G, у которого нет левого узла, но есть правый узел, поэтому, согласно правилу (левый-корень-правый), это null-g-right. Теперь I является правым узлом G, но у I есть левый узел, поэтому обход будет GHI. Это правильно.

Надеюсь, это поможет.

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

Правильный обход был бы следующим: как можно дальше влево по узлам листьев(A), вернуться к родительскому узлу(B), двигаться вправо, но так как у D есть дочерний узел слева от него, вы снова двигаетесь вниз(C), назад вверх к родителю C(D), к правому ребенку D(E), назад к корню(F), двигаться к правому листу(G), двигаться к листу G, но так как у него есть левый листовой узел, двигаться туда(H), вернуться к родителю(I).

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

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

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

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