Cómo recorrer un trabajo de búsqueda binaria e imprimirlo en orden

Primero, debe saber que hay tres formas de atravesar un árbol binario: preordenar , en orden y postorder . Usted menciona el orden, pero como esa es también una frase común en inglés, es posible que no se refiera al orden en el sentido estricto del recorrido del árbol.

Así que veremos los tres, ya que no hace mucha diferencia en el código. Además, no conozco mucho Java, así que lo presentaré de forma genérica y usted mismo podrá convertirlo a Java.

Una manera fácil de implementar un árbol es hacer que cada nodo sea una instancia de una clase. Luego, los métodos del nodo se convierten en los métodos del árbol o cualquier subárbol dentro de él sin ningún esfuerzo adicional.

Entonces tenemos (pseudocódigo):

el nodo de clase hereda el objeto
{
nodo público a la izquierda;
derecho de nodo público;
public void addLeftNode (nodo l);
public void addRightNode (nodo r);
recorrido público vacío (block_t block, order_t m);
};

La implementación de addLeftNode y addRightNode solo asigna la referencia de nodo a algunos miembros de datos privados internos, que son devueltos por izquierda y derecha . Puede construir el árbol de cualquier tamaño que desee. Tenga en cuenta que no he incluido ningún tipo de ‘carga útil’ para el nodo (como su número 57), pero eso se agregaría como otra propiedad, o tal vez como una propiedad de una subclase, como:

clase integerNode hereda el nodo
{
valor entero público;
public void setValue (entero i);
}

Entonces tenemos el método transversal, que es el bit interesante. El recorrido es de propósito general, por lo que he escrito esto de una manera muy genérica. Se necesitan dos parámetros: un block_t , que es algún tipo de puntero o referencia a un bloque ejecutable que usted define en otro lugar, y un parámetro order_t , que es una enumeración para indicar si queremos preordenar, ordenar o postorder. La idea es que se invoque el bloque para cada nodo visitado, y el orden será lo que solicitó. El bloque puede hacer cualquier cosa, por ejemplo, imprimir la propiedad de valor para un Nodo entero.

typedef enum
{
preorden, inorder, postorder
} orden_t;

typedef block_t código void (nodo n);

Aquí está la implementación de traverse ():

atravesar vacío (block_t block, order_t m)
{
if (m == preordenar)
{
bloque (esto);
this.left.traverse (bloque, m);
this.right.traverse (bloque, m);
}
más si (m == orden)
{
this.left.traverse (bloque, m);
bloque (esto);
this.right.traverse (bloque, m);
}
más si (m == postorder)
{
this.left.traverse (bloque, m);
this.right.traverse (bloque, m);
bloque (esto);
}
}

Ojalá esté claro. Para preordenar, llama al bloque, luego recurre a la izquierda y luego a la derecha. Para el orden, primero se repite a la izquierda, luego se llama al bloque, luego se repite a la derecha. Para el pedido posterior, se repite a izquierda y derecha, luego llama al bloque. Si desea atravesar todo el árbol, simplemente invoque el método traverse () en la raíz, y el parámetro order_t dicta el orden de visita del nodo. Tenga en cuenta que se llama a cualquier bloque de tiempo (), el nodo se pasa a sí mismo (‘ esto ‘) como parámetro. Eso permite que el bloque haga lo que quiera usando la interfaz pública del nodo, por lo que este enfoque es locamente simple, pero extremadamente poderoso. Bastante bien, ¿eh?

edit: nb No he incluido una comprobación de la existencia de subnodos izquierdo o derecho. Mi pseudocódigo asume que invocar un método en nil es legal, como lo sería en Objective-C o Swift.

Hay principalmente 3 formas en las que puedes leer un árbol.

1. Recorrido previo al pedido.
2. Recorrido posterior al pedido.
2. Recorrido en orden.

Considere el árbol a continuación y vea la salida de cada recorrido,

Recorrido de preorden: para atravesar un árbol binario en Preorder, se llevan a cabo las siguientes operaciones
(a) Visite el nodo raíz e imprima datos de ese nodo.
(b) Atraviese el subárbol izquierdo, y
(c) Atraviese el subárbol derecho.
Por lo tanto, el recorrido Preorder del árbol de muestra anterior generará: 45 25 15 35 75

Recorrido en orden: para atravesar un árbol binario en orden, se llevan a cabo las siguientes operaciones
(a) Atraviese el subárbol izquierdo,
(b) Visite el nodo raíz e imprima datos de ese nodo, y
(c) Atraviese el subárbol derecho.
Por lo tanto, el recorrido Inorder del árbol de muestra anterior generará: 15 25 35 45 75

Recorrido posterior al pedido: para atravesar un árbol binario en el pedido posterior, se llevan a cabo las siguientes operaciones
(a) Atraviese el subárbol izquierdo,
(b) Atraviese el subárbol derecho, y
(c) Visite el nodo raíz e imprima los datos de ese nodo.
Por lo tanto, el recorrido Postorder del árbol de muestra anterior generará: 15 35 25 75 45

// Impresión de pedidos.
privado vacío printTreeInOrder (Node rootNode) {
if (rootNode == nulo)
regreso;
printTreeInOrder (rootNode.getLeft ());
System.out.print (rootNode.getData () + “”);
printTreeInOrder (rootNode.getRight ());
}

// Preordenar la impresión.
privado vacío printTreePreOrder (Node rootNode) {
if (rootNode == nulo)
regreso;
System.out.print (rootNode.getData () + “”);
printTreePreOrder (rootNode.getLeft ());
printTreePreOrder (rootNode.getRight ());
}

// Impresión posterior al pedido.
privado vacío printTreePostOrder (Node rootNode) {
if (rootNode == nulo)
regreso;
printTreePostOrder (rootNode.getLeft ());
printTreePostOrder (rootNode.getRight ());
System.out.print (rootNode.getData () + “”);
}

Explicación detallada con el programa completo en Java: recorridos de árbol binario – Inorder, Preorder, Postorder, Levelorder

Suponga que tiene la clase Node, entonces la función de viaje será como:

void treeTraverse (nodo de nodo) {
if (nodo == nulo)
regreso;
treeTraverse (nodo.izquierda);
System.out.println (node.value);
treeTraverse (nodo.derecho);
}

Puedes hacerlo de forma iterativa o recursiva. Lo explicaré a través de la recursión, ya que es mucho más sencillo de escribir.

def inOrder (self, node):
si el nodo no es Ninguno:
inOrder (node.left)
print (nodo.val)
inOrder (node.right)

El ejemplo de código anterior está en Python y supone que cada nodo tiene una propiedad izquierda, derecha y de valor. Las propiedades izquierda y derecha apuntarán a los nodos y la propiedad de valor contendrá el valor de los nodos. Mientras nuestro nodo no sea nulo o en el caso de Python, ninguno, finalmente queremos obtener el valor en ese nodo. Después de verificar si el nodo no es None, necesitamos obtener el nodo más a la izquierda, por lo que continuamos pasando el nodo izquierdo a nuestra función inOrder hasta llegar a None. Una vez que eso sucede, el condicional que establecemos ya no se cumple, por lo que volvemos a la llamada anterior de inOrder e imprimimos el valor del nodo. Pasar a inOrder (node.right) también dará lugar a Ninguno, por lo que volveremos a la llamada anterior de inOrder e imprimiremos el valor del nodo. Si hay un nodo correcto, entonces se pasará en una llamada a inOrder. Este patrón continuará hasta que se hayan explorado todos los caminos y se haya alcanzado Ninguno.

EDITAR:

Escribí mi respuesta antes de editar la pregunta y agregar la imagen, pero para tener en cuenta esto, puede asignar valores que correspondan a cada una de las letras. Sin embargo, si está asignando valores de letras en función de su posición en el alfabeto (A = 1, B = 2, …, Z = 26), entonces R no debería estar donde está en su diagrama.

Puede hacerlo de forma iterativa o recursiva, pero la idea básica es imprimir el niño izquierdo, el padre, el niño derecho y luego retroceder y hacer lo mismo nuevamente hasta que haya visitado cada nodo en el BST. En el código se vería algo así (recursivamente):

nulo público en orden (Nodo cur)
{
if (cur! = null)
{
inOrder (cur.left);
System.out.print (cur.data + ”);
inOrder (cur.right);
}
}

Atravesar un BST es lo mismo que atravesar un árbol binario normal porque tiene que visitar todos los nodos y no necesita usar la propiedad BST para el recorrido en orden.

Para un recorrido en orden de árbol binario, puede echar un vistazo al código que se proporciona aquí: Recorrido en orden de un árbol binario

Mira cómo lo harías. Tienes 57 en la raíz, por lo que vas a recorrer todo a la izquierda de eso, imprimiendo a medida que avanzas. Entonces vas a imprimir lo que está en la raíz (57). Luego recorra las cosas hacia la derecha, imprimiendo a medida que avanza.

Por lo tanto, escriba una función llamada printTree que tome un TreeNode y no haga nada si TreeNode es nulo. De lo contrario, debe llamar a printTree para el lado izquierdo, imprimir el valor del nodo y luego llamar a printTree para el lado derecho.