Traversal de pedido de árbol binario en Java
Este es en realidad un árbol binario. Un árbol binario es un árbol donde cada nodo tiene en la mayoría de los dos niños nodos. Si un nodo tiene solo un nodo hijo, ese nodo debe hacerse el nodo izquierdo. Si tiene ambos hijos, entonces hay un nodo izquierdo y un nodo derecho.
Vocabulario de árbol
La explicación del recorrido de árbol se realiza usando vocabulario de árbol.
Nodo raíz: Cada nodo en un árbol tiene un padre excepto el nodo raíz.
Nodos de hoja: Los nodos finales son nodos de hoja. Un nodo de hoja no tiene hijo.
Llave: Este es el valor de un nodo. Puede ser un valor de tipo de datos primitivo o un carácter. También puede ser un operador, e.gramo., + Antiguo Testamento - .
Nivel: Un árbol se organiza en niveles, con el nodo raíz en el primer nivel. Los nodos se pueden imaginar en niveles horizontales. El árbol anterior tiene cuatro niveles.
Nodo principal: El nodo raíz es el único nodo que no tiene un padre. Cualquier otro nodo tiene un nodo principal.
Nodos hermanos: Los hijos de cualquier nodo en particular son nodos hermanos.
Camino: Una ruta es una cadena de nodos y sus ramas individuales.
Nodo del antepasado: Todos los nodos más altos conectados a un niño, incluido el padre y el nodo raíz, son nodos ancestros.
Nodo descendiente: Todos los nodos inferiores, conectados a un nodo particular, directamente a las hojas conectadas, son nodos descendientes. El nodo en cuestión no es parte de los nodos descendientes. El nodo en cuestión no tiene que ser el nodo raíz.
Subtree: Un nodo más todos sus descendientes, hasta las hojas relacionadas, forman un subárbol. El nodo inicial está incluido, y no tiene que ser la raíz; de lo contrario, sería todo el árbol.
Grado: El nodo de un árbol binario puede tener uno o dos hijos. Si un nodo tiene un hijo, se dice que su título es uno. Si tiene dos hijos, se dice que su título es dos.
Este artículo explica cómo atravesar un árbol binario de manera preordenada, utilizando el idioma Java.
Contenido del artículo
- Modelo de traversal
- El enfoque transversal ilustrado
- Clases de java
- El método main ()
- Conclusión
Modelo de traversal
Pedidos
El sub-árbol típico más pequeño de un árbol binario consiste en un nodo principal y nodos para niños. Los nodos infantiles son hermanos formados por el nodo infantil izquierdo y el nodo infantil derecho. Un nodo infantil correcto puede estar ausente.
Hacer un pedido
El nodo principal se visita primero con este pedido, luego el nodo izquierdo y luego el nodo derecho. Si el nodo izquierdo tiene su propio subárbol, entonces se visitarán todos los nodos subárbolas antes de visitar el nodo derecho. Si el nodo correcto tiene su propio subárbol, entonces todo su subárbol se visitará por último. Al visitar un subárbol, se sigue el esquema de pedido anticipado de la derecha de la izquierda matriz para cada triángulo de tres nodos. Si un nodo tiene solo un hijo, lo que significa que no hay un triángulo real, el único niño debe considerarse el nodo izquierdo mientras el nodo derecho está ausente.
Orden de publicación
El nodo izquierdo se visita primero con este pedido, luego el nodo derecho y luego el nodo principal. Si el nodo izquierdo tiene su propio subárbol, entonces se visitarán todos los nodos subárbolas antes de visitar el nodo derecho. Si el nodo correcto tiene su propio subárbol, entonces todo su subárbol se visitará en segundo lugar antes de que se visite el padre. Al visitar un subárbol, se sigue el esquema posterior al orden de la izquierda-derecha para cada triángulo de tres nodos.
En orden
El nodo izquierdo se visita primero con este pedido, luego el nodo principal y luego el nodo derecho. Si el nodo izquierdo tiene su propio subárbol, entonces se visitarán todos los nodos subárbolas antes de visitar el nodo principal. Si el nodo correcto tiene su propio subárbol, entonces todo su subárbol se visitará por último. Al visitar un subárbol, se sigue el esquema en orden de la derecha de los padres izquierdos para cada triángulo de tres nodos.
En este artículo, solo se ilustra el esquema de pedido anticipado.
Recursión o iteración
El esquema de pedido anticipado se puede implementar utilizando la recursión o la iteración. En este artículo, se ilustra la única recursión.
El enfoque transversal ilustrado
En este artículo, se utilizan el esquema de pedido anticipado y la recursión. El diagrama anterior se utilizará. El diagrama se ha vuelto a mostrar aquí para una fácil referencia:
En esta sección, este diagrama se utiliza para mostrar la secuencia de valores (letras) que se muestran (accedidos), utilizando el esquema de pedido y la recursión. Las letras a, b, c, etc., son los valores (claves) de los diferentes nodos.
Preordenar el acceso al árbol comienza desde la raíz. Entonces A es el acceso primero. A tiene dos hijos: B (izquierda) y C (derecha). Preorden es padre-izquierda-derecha. Entonces se accede a B a continuación. Si B nunca tuviera hijos, entonces se accedería a C. Como B tiene hijos: D (izquierda) y E (derecha), se debe acceder a su hijo izquierdo a continuación. Recuerde que el pedido anticipado es padre-izquierda-derecha. Después de B, se accede al padre, se debe acceder a su hijo izquierdo, D, a continuación, de acuerdo con el parent-Leftcild-RightChild.
El triángulo para el nodo principal, b, es bde. En este triángulo, se acaba de acceder al nodo principal, seguido del nodo del hijo izquierdo. El acceso a todos los nodos del triángulo debe completarse primero. Entonces, el siguiente nodo a acceder es el niño correcto del nodo B, que es E E.
Ahora, el triángulo BDE es un subárbol, que es liderado por el nodo B. En este punto, se ha accedido por completo al nodo B y su triángulo. El nodo B es el niño izquierdo del nodo A. El acceso del nodo B y su subárbol se han completado. Siguiendo a los padres izquierda-derecha, después del niño izquierdo, se ha accedido al nodo B, se debe acceder al niño derecho del padre A, C, a continuación.
El triángulo que c de cfg es CFG. C es el padre, F es el niño izquierdo y G es el niño derecho. Entonces, tan pronto como se ha accedido a C, se debe acceder a F de acuerdo con la regla de la derecha de la izquierda matriz. F también tiene un hijo, h. Entonces, tan pronto como se le accede a F, su hijo izquierdo, H, debe ser accedido por la regla de la derecha-derecha de los padres.
Después de eso, F y su subárbol se habrían accedido por completo. En ese momento, no habría duda de acceder a F nuevamente. F es el hijo izquierdo de C, que tiene un niño derecho, G. Después del niño izquierdo, se ha accedido por completo a F, el niño derecho, G, debe ser accedido por la regla de la derecha de la izquierda matriz.
Y así, la secuencia de acceso es: abdecfhg.
Clases de java
El árbol se vuelve a mostrar aquí para una fácil referencia:
Nodo
letra) del nodo. También debe tener otras dos propiedades llamadas izquierda y derecha. A la propiedad izquierda se le asignará un nodo infantil si el nodo tiene un hijo izquierdo. Se le asignará a la propiedad correcta el nodo infantil "A" si el nodo tiene "A" niño correcto.
La clase de nodo necesita un constructor que cree el objeto de nodo y asigne un valor a la clave. El código para la clase es:
nodo de clase
Char Key;
Nodo izquierdo, derecho;
nodo público (valor char)
clave = valor;
izquierda = derecha = nulo;
Cuando se acaba de crear un nodo, no tiene ningún hijo. Es por eso que las propiedades izquierda y derecha se asignan nulos. En el método main (), si un nodo particular tiene un hijo izquierdo, el niño será creado y asignado a la propiedad izquierda del nodo particular. Si un nodo en particular tiene un hijo correcto, el niño será creado y asignado a la propiedad correcta del nodo particular.
La clase de árbol
El código para la clase de árbol es:
Clase BinaryTree
Raíz de nodo;
Árbol binario()
raíz = nulo;
La clase de árbol indica la raíz. Tiene una propiedad llamada raíz, que es para el nodo raíz. Tiene un constructor sin ningún parámetros. Este constructor asigna nulo a la raíz. Cuando se acaba de crear un árbol, no tiene nodo, y es por eso que la raíz de la propiedad es nula. El primer nodo creado será el nodo raíz, y se asignará a esta propiedad, root. A partir de ahí, el árbol crecerá en el método Main () (ver más abajo).
La clase BinaryTree tiene los métodos, preorden () y main () ver a continuación.
El método de pedido anticipado
Este es el núcleo del programa, aunque el método Main () también es importante. El método de pedido previo implementa la regla matriz-izquierda-rightchild. Esta es una función recursiva, cuyo código es:
preorden void (nodo de nodo)
if (nodo == null)
devolver;
// Acceda al nodo principal
Sistema.afuera.imprimir (nodo.clave + "->");
// Acceda al niño izquierdo
reservar (nodo.izquierda);
// Acceda al niño correcto
reservar (nodo.bien);
Al final del transversal del árbol, ningún nodo atravesará, por lo que el valor de cualquier nodo será nulo. Esto representa el primer estado de cuenta en la función de pedido anticipado. La segunda declaración imprime la clave del nodo actual. La tercera declaración recuerda la misma función de pedido de pedido con el nodo infantil izquierdo. La siguiente y última declaración recuerda la función de pedido anticipado con el nodo infantil correcto. De esta manera, todo el árbol está atravesado.
Al mostrar la secuencia, A-> B-> D, después de que se accediera a B, "Preordránete (nodo.correcto) ”se requiere para el nodo C pero reservado. Después de que se haya accedido a D, "Preorden (nodo.correcto) ”se requiere para el nodo E. La llamada para el nodo C, que se reservó, se ejecuta después de eso. Esta explicación se aplica a la rama correcta de todo el árbol.
Y así la secuencia de salida debe ser: a-> b-> d-> e-> c-> f-> h-> g .
El método main ()
El método principal construye el árbol asignando nuevos nodos con sus claves para la propiedad de izquierda o derecha de un nodo principal. Primero, se crea un árbol vacío. Al final del método main (), el método de pedido anticipado se llama una vez. Dado que es una función recursiva, seguirá llamando a sí mismo hasta que todo el árbol haya sido atravesado. El código es:
public static void main (string [] args)
// Crear objeto de árbol sin ningún nodo
Binarytree árbol = new BinaryTree ();
// Crear nodos para el árbol
árbol.raíz = nuevo nodo ('a');
árbol.raíz.izquierda = nuevo nodo ('b');
árbol.raíz.derecho = nuevo nodo ('c');
árbol.raíz.izquierda.izquierda = nuevo nodo ('d');
árbol.raíz.izquierda.derecho = nuevo nodo ('e');
árbol.raíz.bien.izquierda = nuevo nodo ('f');
árbol.raíz.bien.derecho = nuevo nodo ('g');
árbol.raíz.bien.izquierda.izquierda = nuevo nodo ('h');
// Paseo de árbol de árbol de pedido
Sistema.afuera.println ("preorden de traversal");
árbol.preorden (árbol.raíz);
Sistema.afuera.println ();
Todos los códigos anteriores se pueden ensamblar en un solo programa para probar.
La salida es:
A-> b-> d-> e-> c-> f-> h-> g->>
El último -> se puede ignorar.
Conclusión
El recorrido por pedido de árbol binario en Java, que utiliza la recursión, tiene dos clases. Tiene la clase de nodo y la clase binarytree. La clase de nodo tiene una propiedad para la clave. También tiene dos propiedades de nodo para el nodo infantil izquierdo y el nodo infantil derecho. La clase BinaryTree tiene dos métodos: el método preorden () y el método main (). El método preorden () implementa el esquema de los primeros-martillo-rightchild recursivamente. El método Main () construye el árbol asignando nuevos nodos con sus claves como niños izquierdo y derecho a nodos parentales.
El problema con el algoritmo recursivo para preordenar es que si el árbol es demasiado grande, la memoria puede ser corta. Para resolver este problema, use el algoritmo iterativo - ver más tarde.