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

Question

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

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

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

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

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

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

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

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

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

Answer 1

пакет данных;

открытый класс 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());
    }

}

}

пакетная структура данных;

открытый класс Node {

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;
}

}

preOrderTraversal >> 4 2 1 3 6 5 7 inOrderTraversal >> 1 2 3 4 5 6 7 postOrderTraversal >> 1 3 2 5 7 6 4

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

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

К сожалению, ваше понимание неверно.

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