data structures - plantas - Travesía de árboles en orden

nombres e imagenes de arboles

Question

Tengo el siguiente texto de un curso académico que tomé hace un tiempo sobre el recorrido en orden (también lo llaman pancaking) de un árbol binario (no BST):

Travesía de árboles en orden

Dibuja una línea alrededor de la parte exterior del árbol. Comience a la izquierda de la raíz, y vaya alrededor de la parte exterior del árbol, para terminar a la derecha de la raíz. Manténgase lo más cerca posible del árbol, pero no cruce el árbol. (Piense en el árbol, sus ramas y nodos, como una barrera sólida.) El orden de los nodos es el orden en que esta línea pasa por debajo de ellos. Si no está seguro de cuándo va "debajo" de un nodo, recuerde que un nodo "a la izquierda" siempre es lo primero.

Aquí está el ejemplo usado (árbol ligeramente diferente de abajo)

Sin embargo, cuando realizo una búsqueda en google, obtengo una definición conflictiva. Por ejemplo, el ejemplo de wikipedia :

Secuencia transversal de Inorder: A, B, C, D, E, F, G, H, I (leftchild, rootnode, nodo derecho)

Pero de acuerdo con (mi comprensión de) la definición n. ° 1, esto debería ser

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

¿Alguien puede aclarar qué definición es la correcta? Puede que estén describiendo diferentes métodos de cruce, pero que estén usando el mismo nombre. Tengo problemas para creer que el texto académico revisado por pares está mal, pero no puedo estar seguro.

Answer 1

Pero de acuerdo con (mi comprensión de) la definición n. ° 1, esto debería ser

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

Lamentablemente, su comprensión es incorrecta.

Siempre que llegue a un nodo, debe descender a un nodo izquierdo disponible, antes de mirar el nodo actual, luego observa un nodo derecho disponible. Cuando elegiste D antes de C, no descendiste primero al nodo izquierdo.

Answer 2

Ambas definiciones dan el mismo resultado. No te dejes engañar por las letras del primer ejemplo: mira los números a lo largo del camino. El segundo ejemplo usa letras para denotar el camino, quizás eso es lo que te está tirando.

Por ejemplo, en su orden de ejemplo que muestra cómo creía que se atravesaría el segundo árbol con el algoritmo de la primera, coloca "D" después de "B", pero no debería porque todavía hay un nodo secundario de la izquierda de D disponible (es por eso que el primer elemento dice "el orden en que esta línea pasa debajo de ellos".

Answer 3

Creo que el primer árbol binario con la raíz de a es un árbol binario que no está construido correctamente.

Intente implementar de modo que todo el lado izquierdo del árbol sea menor que la raíz y que todo el lado derecho del árbol sea mayor o igual que la raíz.

Answer 4

El recorrido correcto sería: lo más a la izquierda posible con los nodos de las hojas (no los nodos raíz)

Left Root Right

AB NULL

CDE

Nulo FG

HI NULL

F es raíz o izquierda, no estoy seguro

Answer 5

En mi intento malo en el sorteo aquí está el orden que muestra cómo deben ser recogidos.

más o menos elige el nodo que está directamente sobre la línea que se está dibujando.

Answer 6

Es correcto para preorder, nt para inorder

Answer 7

Olvídese de las definiciones, es mucho más fácil aplicar el algoritmo:

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

Son solo tres líneas. Reorganiza el orden para pre y post orden.

Answer 8

Oye, según lo que mencioné en wiki, es correcto, la secuencia para un recorrido inorden es izquierda-raíz-derecha.

Hasta A, B, C, D, E, F creo que ya lo has entendido. Ahora, después de la raíz F, el siguiente nodo es G que no tiene un nodo izquierdo sino un nodo derecho, por lo que según la regla (izquierda-raíz-derecha) es nulo-g-derecha. Ahora yo soy el nodo derecho de G pero tengo un nodo izquierdo, por lo tanto, el cruce sería GHI. Esto es correcto.

Espero que esto ayude.

Answer 9

Para un cruce de árboles en línea, debe tener en cuenta que el orden de recorrido es el nodo izquierdo-derecho. Para el diagrama anterior en el que está en conflicto, su error se produce cuando lee un nodo padre antes de leer cualquier nodo hoja (secundarios) a la izquierda.

El recorrido correcto sería: lo más a la izquierda posible con los nodos hoja (A), regrese al nodo padre (B), muévase hacia la derecha, pero como D tiene un niño a su izquierda, vuelve a bajar (C), copia de seguridad al padre de C (D), al hijo derecho de D''E (E), retroceda a la raíz (F), muévase a la hoja derecha (G), muévase a la hoja de G, pero como tiene un nodo de hoja izquierda muévase allí (H) , regreso a los padres (I).

el recorrido anterior lee el nodo cuando lo tengo enumerado entre paréntesis.

Answer 10

Personalmente encontré esta conferencia bastante útil.

Answer 11

Si lees detenidamente, verás que la primera "definición" dice que comienza a la izquierda de la raíz y que el orden de los nodos está determinado por cuando pasas por debajo de ellos. Así que B no es el primer nodo, ya que lo pasas de la izquierda en el camino hacia A , luego pasas primero por debajo de A luego subes y pasas por debajo de B Por lo tanto, parece que ambas definiciones dan el mismo resultado.

Answer 12

esto puede ser tarde, pero podría ser útil para cualquier persona más tarde ... simplemente no necesita ignorar los nodos ficticios o nulos, por ejemplo, el Nodo G tiene un nodo nulo a la izquierda ... teniendo en cuenta que este nodo nulo lo hará todo bien ...

Answer 13

estructura de datos del paquete;

clase pública 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());
    }

}

}

estructura de datos del paquete;

nodo de clase pública {

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 14

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

Este es el enfoque más simple para la definición recursiva de recorrido transversal, simplemente llame a esta función en la función principal para obtener el recorrido en orden de un árbol binario dado.