Tutorial de estructura de datos de árbol para principiantes

Introducción

Un árbol en el software es como un árbol biológico, pero con las siguientes diferencias:

• Se dibuja al revés.
• Tiene una sola raíz y no tiene tallo.
• Las ramas emergen de la raíz.
• Un punto donde una rama despega de otra rama o la raíz se llama nodo.
• Cada nodo tiene un valor.

Las ramas del árbol del software están representadas por líneas rectas. Un buen ejemplo de un árbol de software que podría haber utilizado es el árbol de directorios del disco duro de su computadora.

Hay diferentes tipos de arboles. Existe el árbol general del que se derivan otros árboles. Otros árboles se derivan mediante la introducción de restricciones en el árbol general. Por ejemplo, es posible que desee un árbol en el que no emanen más de dos ramas de un nodo; tal árbol se llamaría árbol binario.  Este artículo describe el árbol general y cómo acceder a todos sus nodos.

El hipervínculo para descargar el código se encuentra al final de este artículo.

Para comprender los ejemplos de código de este artículo, debe tener conocimientos básicos en JavaScript (ECMAScript). Si no tiene ese conocimiento, puede obtenerlo en http: // www.amplia red.com / ChrysanthusForcha-1 / ECMAScript-2015-Course.htm

El diagrama de árbol general

'A' es el nodo raíz; es el nodo de primer nivel. B, C, D están en la segunda línea; estos son nodos de segundo nivel. E, F, G, H, I, J, K están en la tercera línea y son nodos de tercer nivel. Una cuarta línea habría producido nodos de cuarto nivel, y así sucesivamente.

Propiedades del árbol

- Todas las ramas para todos los niveles de nodos tienen una fuente, que es el nodo raíz.

- Un árbol tiene N - 1 ramas, donde N es el número total de nodos. El diagrama anterior para el árbol general tiene 11 nodos y 10 ramas.

- A diferencia de los humanos, donde cada niño tiene dos padres, con el árbol de software, cada niño tiene solo un padre. El nodo raíz es el principal antepasado. Un padre puede tener más de un hijo. Cada nodo, excepto el nodo raíz, es un hijo.

Vocabulario de árboles

• Nodo raíz: Este es el nodo más alto del árbol y no tiene padre. Cada otro nodo tiene un padre.
• Nodos de hoja: Un nodo hoja es un nodo que no tiene hijos. Por lo general, se encuentran en la parte inferior del árbol y, a veces, en los lados izquierdo y / o derecho del árbol.
• Clave: Este es el valor de un árbol. Puede ser un número; puede ser una cuerda; incluso puede ser un operador como + o - o x.
• Niveles: El nodo raíz está en el primer nivel. Sus hijos están en el segundo nivel; Los hijos de los nodos de segundo nivel están en el tercer nivel, y así sucesivamente.
• Nodo principal: Cada nodo, excepto el nodo raíz, tiene un nodo padre conectado a él por una rama. Cualquier nodo, excepto el nodo raíz, es un nodo hijo.
• Nodos hermanos: Los nodos hermanos son nodos que tienen el mismo padre.
• Camino: Las ramas (líneas rectas) que conectan un nodo con otro, a través de otros nodos, forman un camino. Las ramas pueden ser flechas o no.
• Nodo ancestro: Todos los nodos superiores conectados a un hijo, incluidos el padre y el nodo raíz, son nodos ancestros.
• Nodo descendiente: Todos los nodos inferiores conectados a un nodo, hasta las hojas conectadas, son nodos descendientes. El nodo en cuestión no forma parte de los nodos descendientes. El nodo en cuestión, no tiene que ser el nodo raíz.
• Subárbol: 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.
• La licenciatura: El número de hijos que tiene un nodo se llama grado del nodo.

Atravesando todos los nodos de un árbol

Se puede acceder a todos los nodos de un árbol para leer o cambiar cualquier valor del nodo. Sin embargo, esto no se hace de forma arbitraria. Hay tres formas de hacer esto, todas las cuales implican el recorrido en profundidad primero de la siguiente manera:

1) En orden: En pocas palabras, en este esquema, primero se atraviesa el subárbol izquierdo; luego, se accede al nodo raíz; luego, se atraviesa el subárbol derecho. Este esquema se simboliza como izquierda-> raíz-> derecha. La figura 1 se vuelve a mostrar aquí para una fácil referencia:

Suponiendo que hay dos hermanos por nodo; luego izquierda-> raíz-> derecha significa, primero accede al nodo más bajo y más a la izquierda, luego al padre del nodo y luego al hermano derecho. Cuando hay más de dos hermanos, tome el primero como el izquierdo y el resto de los nodos derechos, como el derecho. Para el árbol general anterior, se accede al subárbol inferior izquierdo para tener, [EBF]. Este es un subárbol. El padre de este subárbol es A; por lo que, a continuación, se accede a A para tener [EBF] A. A continuación, se accede al subárbol [GCHI] para tener un subárbol más grande, [[EBF] A [GCHI]]. Puede ver el perfil izquierdo-> raíz-> derecho retratándose a sí mismo. Este gran subárbol izquierdo tendrá el subárbol, [JDK] a su derecha para completar el recorrido para obtener, [[EBF] A [GCHI]] [JDK].

2) Pedido anticipado: En pocas palabras, en este esquema se accede primero al nodo raíz, luego se atraviesa el subárbol izquierdo y luego se atraviesa el subárbol derecho. Este esquema se simboliza como raíz-> izquierda-> derecha. La figura 1 se vuelve a mostrar aquí para facilitar la referencia.

Suponiendo que hay dos hermanos por nodo; luego root-> left-> right significa, primero accedes a la raíz, luego al hijo inmediato izquierdo y luego al hijo inmediato derecho. Cuando hay más de dos hermanos, tome el primero como el izquierdo y el resto de los nodos derechos, como el derecho. El hijo más a la izquierda del hijo izquierdo es el siguiente al que se accede. Para el árbol general anterior, el subárbol raíz es [ABCD]. A la izquierda de este subárbol, tiene el subárbol, [EF], que proporciona la secuencia de acceso, [ABCD] [EF]. A la derecha de este subárbol más grande, tiene dos subárboles, [GHI] y [JK], dando la secuencia completa, [ABCD] [EF] [GHI] [JK]. Puede ver el perfil raíz-> izquierda-> derecha retratándose a sí mismo.

3) Pedido posterior: En pocas palabras, en este esquema, primero se atraviesa el subárbol izquierdo, luego se atraviesa el subárbol derecho y luego se accede a la raíz. Este esquema se simboliza como izquierda-> derecha-> raíz. La figura 1 se vuelve a mostrar aquí para facilitar la referencia.

Para este árbol, los subárboles son [EFB], [GHIC], [JKD] y [A] que forman la secuencia, [EFB], [GHIC], [JKD] [A]. Puede ver el perfil de la izquierda-> derecha-> raíz retratándose a sí mismo.

Creando el árbol

El árbol anterior se creará utilizando ECMAScript, que es como la última versión de JavaScript. Cada nodo es una matriz. El primer elemento de cada matriz de nodos es el padre del nodo, otra matriz. El resto de los elementos del nodo son los hijos del nodo, comenzando por el hijo situado más a la izquierda. Hay un mapa ECMAScript que relaciona cada matriz con su correspondiente cadena (letra). El primer segmento de código es: