Обход дерева порядка: какое определение правильное?

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

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

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

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 NULL

C D E

Нуль F G

H I NULL

F - корень или левый, я не уверен

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

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

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

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

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

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

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

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

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

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

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

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

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

public class 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());
    }

}

}

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

public class 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

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

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

Правильно для предзаказа, нет для inorder