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 solo una raíz y sin 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 de 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 directorio del disco duro de su computadora.

Hay diferentes tipos de árboles. Existe el árbol general del que se derivan otros árboles. Otros árboles se derivan introduciendo restricciones en el árbol general. Por ejemplo, es posible que desee un árbol donde no emanen más de dos ramas de un nodo; Tal árbol se llamaría un á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 da en la parte inferior de este artículo.

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

El diagrama general de árboles

'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 de los árboles

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

- Un árbol tiene ramas n - 1, 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 solo tiene un padre. El nodo raíz es el mejor padre antepasado. Un padre puede tener más de un hijo. Cada nodo, excepto el nodo raíz, es un niño.

Vocabulario de árbol

• Nodo raíz: Este es el nodo más alto del árbol, y no tiene padres. Cualquier otro nodo tiene un padre.
• Nodos de hoja: Un nodo de hoja es un nodo que no tiene hijo. Por lo general, están en el fondo del árbol y a veces están en los lados izquierdo y/o derecho del árbol.
• Llave: Este es el valor de un árbol. Puede ser un número; Puede ser una cadena; 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 niños 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 principal conectado por una rama. Cualquier nodo, excepto el nodo raíz, es un nodo infantil.
• Nodos hermanos: Los nodos hermanos son nodos que tienen el mismo padre.
• Camino: Las ramas (líneas rectas) que conectan un nodo a otro, a través de otros nodos, forman una ruta. Las ramas pueden o no ser flechas.
• Nodo 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, justo hasta 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.
• 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.
• Grado: El número de niños que tiene un nodo se llama el 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 arbitrariamente. Hay tres formas de hacer esto, todas las cuales implican una transversal de profundidad de la siguiente manera:

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

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

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

Suponiendo que hay dos hermanos por nodo; luego raíz-> izquierda-> significa que accederá primero a la raíz, luego al niño inmediato izquierdo y luego al niño inmediato derecho. Cuando hay más de dos hermanos, tome el primero como la izquierda y el resto de los nodos correctos, como la derecha. El niño más izquierdo del niño izquierdo es el siguiente en acceder. Para el árbol general de arriba, el subárbol raíz es [ABCD]. A la izquierda de este subárbol, tiene el subárbol, [ef], dando la secuencia de acceso, [ABCD] [EF]. A la derecha de este subárbol más grande, tienes dos subárboles, [ghi] y [jk], dando la secuencia completa, [abcd] [ef] [ghi] [jk]. Puedes ver el perfil de raíz-> izquierda-> retratándose a sí mismo.

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

Para este árbol, los subárboles son, [efB], [Ghic], [jkd] y [a] que forman la secuencia, [efb], [ghic], [jkd] [a]. Puedes ver el perfil de raíz izquierda-> derecha-> retratarse a sí mismo.

Creando el árbol

El árbol anterior se creará usando EcMascript, que es como la última versión de JavaScript. Cada nodo es una matriz. El primer elemento de cada matriz de nodo es el padre del nodo, otra matriz. El resto de los elementos del nodo son los hijos del nodo, que comienzan desde el niño más a la izquierda. Hay un mapa de Ecmascript que relaciona cada matriz con su cadena correspondiente (letra). El primer segmento de código es:

O = nueva matriz ();
A = nueva matriz ();
B = nueva matriz ();
C = nueva matriz ();
D = nueva matriz ();
//hojas
E = nueva matriz (b); F = nueva matriz (b); G = nueva matriz (c); H = nueva matriz (c);
I = nueva matriz (c); J = nueva matriz (d); K = nueva matriz (d);
// Agregar el contenido
O [0] = indefinido; O [1] = a;
A [0] = o; A [1] = b; A [2] = c; A [3] = D;
B [0] = a; B [1] = E; B [2] = f;
C [0] = a; C [1] = g; C [2] = H; C [3] = i;
D [0] = a; D [1] = j; D [2] = k;
// Mapeo de objetos a letras
pares = [[a, 'a'], [b, 'b'], [c, 'c'], [d, 'd'], [e, 'e'], [f, 'f'] , [G, 'G'],
[H, 'h'], [i, 'i'], [j, 'j'], [k, 'k']];
mapobj = nuevo mapa (pares);

En ECMAScript, puede acceder a una función que se define de manera baja en el programa. Sin embargo, con variables, no puedes hacer eso. No puede acceder a una variable que se define más abajo en el programa. Esta es la razón por la cual las variables anteriores se han desarrollado como se muestra.

Además, tenga en cuenta que por encima del nodo raíz A, hay otro nodo o (no cero). El primer elemento de esta matriz (nodo) está indefinido, lo que significa que su propio padre está indefinido. El nodo adicional se ha agregado para facilitar el código de recorrido.

También hay un mapa. El mapa relaciona cada matriz de nombres de una letra, con el nombre de cadena correspondiente de una letra.

Función recursiva

Para acceder a todos los elementos de un árbol, necesita una función recursiva. Una función recursiva es una función que sigue llamando a sí misma hasta que se cumple una condición.

Visitar un nodo no significa necesariamente acceder al nodo. Acceder a un nodo significa que su valor se lee o cambia. En las muestras de código de este artículo, acceder a un nodo significa leer y mostrar el valor (clave) del nodo. En las muestras de código, se puede visitar un nodo más de una vez, pero solo se accede a su valor una vez.

Algoritmo y programación

Hay un programa para cada una de las tres técnicas de recorrido.

Algoritmo y programación en orden

Aquí, el nodo más bajo y a la izquierda se visita primero. Los subárboles [EBF], [[EBF] A [GCHI]] y [JDK] se desarrollan para dar la secuencia completa, [[EBF] A [GCHI]] [JDK].

Hay dos funciones recursivas para este programa, donde cada una llama al otro. El principal se llama Fn (nodo). El programa (código) es corto. Descargue el archivo combinado a continuación para la codificación de detalles.

Los tres programas tienen la misma configuración de árbol de matriz (nodo).

Algoritmo y programación de pedido anticipado

Aquí, solo hay una función recursiva. Se llama, fn (nodo). Aquí, los subárboles [ABCD], [ef], [GHI] y [JK] se desarrollan para dar la secuencia completa, [ABCD] [EF] [GHI] [JK]. El programa para esto también es corto.

Los tres programas tienen la misma configuración de árbol de matriz (nodo).

Algoritmo y programación posterior a la orden

Aquí, el nodo más bajo y a la izquierda se visita primero. Los subárboles [EFB], [Ghic], [JKD] y [A] se desarrollan para dar la secuencia completa, [EFB], [Ghic], [JKD] [A] .

Hay dos funciones recursivas para este programa, donde cada una llama al otro. El principal se llama Fn (nodo). El programa para esto también es corto. Descargue el archivo combinado a continuación para la codificación detallada.

Los tres programas tienen la misma configuración de árbol de matriz (nodo).

Tipos de árboles

Los árboles de programación de computadoras son, de hecho, estructuras de datos no lineales. Las estructuras de datos lineales son listas, matrices, pilas, colas, pilas, etc. Un árbol con nodos n tiene ramas N-1. Cuando el número de ramas es igual o mayor que el número de nodos, se obtiene un gráfico. Un gráfico no es realmente un árbol.

Hay árboles de software, que describen diseños, como el árbol de directorio en el disco duro de una computadora. Muchos árboles no describen los diseños existentes en absoluto. De hecho, describen algoritmos. Por ejemplo, el árbol del algoritmo matemático (x + y) x (x -y) se describe mediante un árbol donde x es el nodo raíz, entonces + y - son nodos infantiles inmediatos de la raíz. x e y son nodos infantiles de +. x e y son de nuevo nodos infantiles de -. Tal árbol se conoce como un árbol de expresión.

Muchos tipos diferentes de árboles se pueden clasificar en diferentes encabezados; como árbol binario, árbol B, árbol de expresión, etc. Todos ellos se derivan del árbol general.

Algunas de las categorías de árboles se dividen en otras categorías. El árbol binario, por ejemplo, tiene al menos el árbol de búsqueda binario, el árbol AVL y el árbol cartesiano.

Descarga

Se han proporcionado tres programas para este artículo. Hay un programa para la técnica en orden (algoritmo), otro para la técnica de pedido anticipado y otro para la técnica posterior al pedido. Todos ellos han sido colocados en un archivo zip, llamado recorrido. El archivo zip se puede descargar en: github.

Conclusión

Un árbol de software es como un árbol normal en el parque o en el bosque. Sin embargo, el árbol de programación de computadoras está al revés. Hay diferentes tipos de árboles. Otros árboles se derivan introduciendo restricciones en el árbol general. Se puede acceder a todos los nodos de un árbol utilizando un algoritmo en orden, pre-pedido o posterior a. Un árbol de software puede ser producido por cualquier lenguaje de computadora. Ecmascript ha sido elegido aquí porque es el lenguaje de computadora más simple. El siguiente tipo de árbol que debe estudiar es el árbol binario, ya que es la estructura de datos del árbol más popular.