Cómo hacer un recorrido en orden de un Árbol Binario en Java

Escrito por ehow contributor | Traducido por enrique pereira vivas
  • Comparte
  • Twittea
  • Comparte
  • Pin
  • E-mail
Cómo hacer un recorrido en orden de un Árbol Binario en Java
(computer image by blaine stiger from Fotolia.com)

Java no tiene una clase de árbol binario, aunque es fácil de presentar una versión de la estructura de datos para hacer un recorrido en orden. Un "recorrido" de un árbol binario es un procedimiento fórmula para visitar cada nodo en el árbol binario una vez. Un recorrido en orden hará esto de forma ordenada. A menudo, el recorrido se implementa como una especie de repetidor (como un iterador de una lista) o por un método que solicitará devolución de llamada para cada nodo. Sin embargo, puedes hacer esto sin usar las devoluciones de llamada o iteradores, en lugar de imprimir a la consola cada nodo visitado.

Nivel de dificultad:
Moderado

Otras personas están leyendo

Instrucciones

  1. 1

    Crea una búsqueda binaria básica de clase de árbol. En este punto, sólo necesitarás un método constructor básico que inicialice el valor del nodo y un método de inserción. El método de inserción recorrerá un árbol y creará un nuevo nodo en el lugar correcto. ""public class BinaryTree { BinaryTree left; BinaryTree right; int value; public BinaryTree(int v) { value = v; } // Introduce un valor en el vacío público del árbol insert(int v) { if(v < value) { if(left == null) left = new BinaryTree(v); else left.insert(v); } else if(v > value) { if(right == null) right = new BinaryTree(v); else right.insert(v); } }}""

  2. 2

    Crea la instancia (nodo) del árbol binario que será el nodo raíz. Al igual que cualquier otro nodo, el nodo raíz tiene que tener un valor. Por lo general, es mejor elegir un valor cercano a la mediana de los objetos que estás almacenando, ya que los árboles binarios deben ser lo más equilibrado posible. ""BinaryTree b = new BinaryTree(50);""

  3. 3

    Inserta nodos en el árbol en un orden específico para mantener el equilibrio, ya que este árbol binario no se auto-equilibra. Este ejemplo crea el árbol más pequeño posible con el fin de mantener la eficiencia. ""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);""

  4. 4

    Muévete a través del árbol mediante un recorrido en orden. El árbol de la izquierda es atravesado en primer lugar, seguido por el nodo raíz, y luego el árbol de la derecha es atravesado. Usando la recursividad, el código no será de más de tres líneas. Sin embargo, dado que la recursividad toma espacio de la pila, debe usarse con cuidado. Con un árbol binario pequeño y equilibrado, la recursividad no desbordará la pila.

  5. 5

    Añade un nuevo método para la clase Java de Árbol Binario Java llamado en orden. ""public void inorder() { if(left != null) left.inorder(); System.out.println(value); if(right != null) right.inorder();}""

  6. 6

    Llama al método en orden después de tus insertos para imprimir los nodos en el orden establecido. ""b.inorder();"

Consejos y advertencias

  • Métodos como un "nodo delete" método no son compatibles con esta clase de ejemplo.
  • En este ejemplo de recorrido en orden, la pila no hará sino crecer a la altura del árbol, por lo que la pila no se desbordará. Si tu árbol binario es muy grande, la función de recorrido debe aplicarse de forma iterativa.
  • Como con cualquier otro lenguaje de programación, los árboles binarios desequilibrados en Java pueden llegar a ser muy altos y son ineficaces.

No dejes de ver

Filtrar por:
  • Mostrar todos
  • Artículos
  • Galerías de fotos
  • Videos
Ordenar:
  • Más relevante
  • Más popular
  • Más reciente

No se encuentran artículos disponibles

No se encuentran slideshows disponibles

No se encuentran videos disponibles