¿Cómo hacer orden final de recorrido en un árbol binario en Java

Aunque Java no proporciona una clase de árbol binario en las bibliotecas predeterminadas, una clase de árbol binario básico es simple suficiente para ser presentado. A "recorrido" de una estructura de datos es un algoritmo que visita cada nodo de una vez. Esto a menudo se implementa como una cierta clase de iterador (como un iterador de lista) o un método que se llame a un método de devolución de llamada para cada nodo. En Java, hay que hacer un recorrido en "orden posterior", que visitará el nodo raíz última, no se necesitan ni devoluciones de llamada o iteradores. La función de recorrido simplemente imprimir cada nodo que visita a la consola.

Instrucciones

1 Escribir una clase de árbol binario de búsqueda básica. Sólo hay dos métodos que necesitan ser apoyado en esta etapa: un constructor de base que inicializa el valor del nodo, y un método de inserción. El método de inserción será recorrer un árbol y crear un nuevo nodo en el lugar correcto. ""public class BinaryTree {
BinaryTree left;
BinaryTree right;
int value;

else if(v > value) {
if(right == null)
right = new BinaryTree(v);
else
right.insert(v);
}
}"" ""public class BinaryTree {
BinaryTree left;
BinaryTree right;
int value;

else if(v > value) {
if(right == null)
right = new BinaryTree(v);
else
right.insert(v);
}
}""

2 Crear una instancia de la árbol binario que será el nodo raíz. Cada nodo, incluso el nodo raíz, debe tener un valor.

3 Elija un valor para el nodo raíz que está en algún lugar en medio de los objetos que va a guardarlo. Por ejemplo, si usted está almacenando una distribución uniforme de los números del 1 al 100, 50 es una buena opción para el nodo raíz. Árboles binarios deben ser lo más equilibrada posible, ya que los árboles crecen muy desequilibradas alto y no son muy eficaces. ""BinaryTree b = new BinaryTree(50);""

4 Insertar algunos nodos en el árbol. Desde este árbol no es auto-equilibrio, para conservar el equilibrio, los nodos deben insertarse en un orden específico. El orden en este ejemplo de código se hace a mano para hacer que el árbol más corto y más eficiente posible. ""b.insert(20);
b.insert(40);
b.insert(10);
b.insert(5);
b.insert(45);

b.insert(70);
b.insert(60);
b.insert(80);
b.insert(55);
b.insert(85);"" ""b.insert(20);
b.insert(40);
b.insert(10);
b.insert(5);
b.insert(45);

b.insert(70);
b.insert(60);
b.insert(80);
b.insert(55);
b.insert(85);""

5 Traverse el árbol, atravesando el árbol de la izquierda primero, seguido por el árbol de la derecha, y, finalmente, el nodo raíz. Si se utiliza la recursividad para hacer el recorrido de orden posterior, el método es de sólo tres líneas de largo. En este caso, la pila sólo crecerá a la altura del árbol. Dado que el árbol está equilibrado y pequeña, la recursividad no se desborde la pila.

6 Añadir un nuevo método a la clase llamada BinaryTree orden posterior. Aquí, sólo se imprime el valor de cada nodo que visita. ""public void postorder() {
if(left != null) left.postorder();
if(right != null) right.postorder();
System.out.println(value);
}"" ""public void postorder() {
if(left != null) left.postorder();
if(right != null) right.postorder();
System.out.println(value);
}""

7 Imprimir los nodos en orden posterior llamando al método b.postorder después de sus inserciones.

""b.postorder();"

Consejos y advertencias

• Desde la recursividad toma espacio de pila, lo que debe utilizarse con cuidado. Si su árbol binario es muy grande, la función de recorrido debe ser implementado de forma iterativa.
• El método más complicado "nodo de eliminación" no es compatible con esta clase de ejemplo.