Обход дерева по порядку:Какое определение является правильным?
https://stackoverflow.com/questions/486039
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть следующий текст из академического курса, который я прослушал некоторое время назад, о обходе inorder (они также называют это pancaking) бинарное дерево (не BST):
Обход дерева по порядку
Нарисуйте линию вокруг внешней стороны дерева .Начните слева от корня, и обойдите дерево снаружи, чтобы оказаться справа от корня.Держитесь как можно ближе к дереву, но не перелезайте через дерево.(Представьте себе дерево — его ветви и узлы — как сплошной барьер.) Порядок расположения узлов - это порядок, в котором эта линия проходит под ними.Если вы не уверены в том, когда вы переходите “под” узел, помните, что узел “слева ” всегда идет первым.
Вот использованный пример (немного отличающееся дерево от приведенного ниже)
Однако, когда я выполняю поиск в Google, я получаю противоречивое определение.Например , в пример из Википедии:
Последовательность обхода по порядку:A, B, C, D, E, F, G, H, I (левый дочерний элемент, корневой узел, правый узел)
Но согласно (моему пониманию) определению № 1, это должно быть
A, B, D, C, E, F, G, I, H
Кто-нибудь может уточнить, какое определение является правильным? Возможно, они оба описывают разные методы обхода, но случайно используют одно и то же имя.Мне трудно поверить, что рецензируемый академический текст ошибочен, но я не могу быть уверен.
Решение
В моей неудачной попытке нарисовать вот порядок, который показывает, как их следует выбирать.
в значительной степени выберите узел, который находится непосредственно над рисуемой линией,.
Другие советы
Забудьте об определениях, гораздо проще просто применить алгоритм:
void inOrderPrint(Node root)
{
if (root.left != null) inOrderPrint(root.left);
print(root.name);
if (root.right != null) inOrderPrint(root.right);
}
Это всего лишь три строчки.Измените порядок предварительного и последующего заказа.
Если вы внимательно прочтете, то увидите, что в первом "определении" говорится о начале слева корня и что порядок узлов определяется тем, когда вы передаете под их.Итак B не является первым узлом, так как вы проходите его слева по пути к A, затем первый проход под A после чего вы поднимаетесь и проходите под B.Поэтому кажется, что оба определения дают один и тот же результат.
Я лично нашел эта лекция весьма полезно.
Оба определения дают один и тот же результат.Не обманывайтесь тем, что письма в первом примере - посмотрите на цифры вдоль пути.Во втором примере действительно используются буквы для обозначения пути - возможно, именно это сбивает вас с толку.
Например, в вашем примере порядка, показывающем, как вы думали, что второе дерево будет пройдено с использованием алгоритма первого, вы помещаете "D" после "B", но вы не должны этого делать, потому что все еще доступен левый дочерний узел D (вот почему в первом элементе указано "порядок, в котором проходит эта строка под ним их".
это может быть поздно , но позже это может пригодиться кому угодно ..вам просто не нужно игнорировать фиктивные или нулевые узлы, например, Узел G имеет левый нулевой узел ..учитывая этот нулевой узел , все будет в порядке ..
Правильный обход был бы:как можно дальше влево с конечными узлами (не корневыми узлами)
Левый Корень Правый
A B НУЛЕВОЙ
C D E
Ноль F G
H I НУЛЬ
F - это корень или левый, я не уверен
Я думаю, что первое двоичное дерево с корнем a это двоичное дерево, которое построено неправильно.
Попробуйте реализовать так, чтобы вся левая сторона дерева была меньше корня, а вся правая сторона дерева была больше или равна корню.
Но согласно (моему пониманию) определение #1, это должно быть
A, B, D, C, E, F, G, I, H
К сожалению, ваше понимание неверно.
Всякий раз, когда вы прибываете на узел, вы должны спуститься к доступному левому узлу, прежде чем смотреть на текущий узел, затем вы смотрите на доступный правый узел.Когда вы выбрали D перед C, вы сначала не спустились к левому узлу.
Эй, по моему мнению, как упомянуто в wiki, правильная последовательность для обхода по порядку - left-root-right.
До A, B, C, D, E, F, я думаю, вы уже поняли.Теперь после root F следующим узлом является G, у которого есть не левый узел, а правый узел, так что согласно правилу (left-root-right) его null-g-right .Теперь I является правым узлом G, но у I есть левый узел, следовательно, обход был бы GHI .Это правильно.
Надеюсь, это поможет.
Для обхода встроенного дерева вы должны иметь в виду, что порядок обхода - левый-узел-правый.Для приведенной выше диаграммы, на которой у вас конфликт, ваша ошибка возникает, когда вы читаете родительский узел перед чтением любых конечных (дочерних) узлов слева.
Правильный обход был бы:как можно дальше влево с конечными узлами (A), вернитесь к родительскому узлу (B), переместитесь вправо, но поскольку у D есть дочерний узел слева, вы снова перемещаетесь вниз (C), возвращаетесь к родительскому узлу C (D), к правому дочернему узлу D (E), возвращаетесь к корневому (F), перемещаетесь к правому листу (G), перемещаетесь к листу G, но поскольку у него есть левый конечный узел, перемещаетесь туда (H), возвращаетесь к родительскому (I).
приведенный выше обход считывает узел, когда я указываю его в круглых скобках.
структура данных пакета;
открытый класс BinaryTreeTraversal {
public static Node<Integer> node;
public static Node<Integer> sortedArrayToBST(int arr[], int start, int end) {
if (start > end)
return null;
int mid = start + (end - start) / 2;
Node<Integer> node = new Node<Integer>();
node.setValue(arr[mid]);
node.left = sortedArrayToBST(arr, start, mid - 1);
node.right = sortedArrayToBST(arr, mid + 1, end);
return node;
}
public static void main(String[] args) {
int[] test = new int[] { 1, 2, 3, 4, 5, 6, 7 };
Node<Integer> node = sortedArrayToBST(test, 0, test.length - 1);
System.out.println("preOrderTraversal >> ");
preOrderTraversal(node);
System.out.println("");
System.out.println("inOrderTraversal >> ");
inOrderTraversal(node);
System.out.println("");
System.out.println("postOrderTraversal >> ");
postOrderTraversal(node);
}
public static void preOrderTraversal(Node<Integer> node) {
if (node != null) {
System.out.print(" " + node.toString());
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
public static void inOrderTraversal(Node<Integer> node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(" " + node.toString());
inOrderTraversal(node.right);
}
}
public static void postOrderTraversal(Node<Integer> node) {
if (node != null) {
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(" " + node.toString());
}
}
}
структура данных пакета;
узел открытого класса {
E value = null;
Node<E> left;
Node<E> right;
public E getValue() {
return value;
}
public void setValue(E value) {
this.value = value;
}
public Node<E> getLeft() {
return left;
}
public void setLeft(Node<E> left) {
this.left = left;
}
public Node<E> getRight() {
return right;
}
public void setRight(Node<E> right) {
this.right = right;
}
@Override
public String toString() {
return " " +value;
}
}
Предварительный заказ в обратном направлении >> 4 2 1 3 6 5 7 В обратном порядке >> 1 2 3 4 5 6 7 После обратного заказа >> 1 3 2 5 7 6 4
void
inorder (NODE root)
{
if (root != NULL)
{
inorder (root->llink);
printf ("%d\t", root->info);
inorder (root->rlink);
}
}
Это самый простой подход к рекурсивному определению обхода по порядку, просто вызовите эту функцию в функции main, чтобы получить обход по порядку данного двоичного дерева.
Это правильно для предварительного заказа, nt для inorder
