Un árbol es un tipo especial de relación que es muy útil para el estudio de una gran variedad de aplicaciones en las ciencias de la computación e ingeniería. Un árbol se representa como un grafo dirigido o no dirigido. Los árboles son muy usados en el estudio y construcción de base de datos, modelamiento jerárquico de clases y en la teoría de lenguajes y construcción de compiladores, son muy usados para describir los árboles sintácticos correspondientes a gramáticas de lenguajes. Puede tomarse como un árbol de n elementos asociados a cada uno de sus componentes.
Un árbol n-ario es una estructura recursiva, en la cual cada elemento tiene un número cualquiera de árboles n-arios asociados. Estos árboles corresponden a la generalización de un árbol binario. La diferencia radica en que esta estructura puede manejar múltiples subárboles asociados a cada elemento, y no solamente 2, como en el caso de los árboles binarios.
Conceptos
• Nodo: elemento del árbol.
• Raíz: nodo inicial del árbol.
• Hoja: nodo sin hijos.
• Camino: nodos entre dos elementos incluyéndolos
• Rama: camino entre la raíz y una hoja.
• Altura: número de nodos en la rama más larga
• Peso: número de nodos en el árbol
• Máximo orden de sus elementos.
Los recorridos definidos para los ´arboles generales también se aplican a los ´arboles m-arios. Además, en el caso de los ´arboles binarios se define el recorrido en inorden: se visita en primer lugar el subárbol izquierdo, a continuación, la raíz, y finalmente el subárbol derecho.
A continuación, la representación gráfica de un árbol n ario.
Siendo a el nodo raíz del árbol, b, c y d la lista de hijos de este nodo, e y f es la lista de hijos del nodo c y d contiene un único hijo en la lista de enlaces, por último, h, i, j y k son los hijos del nodo e. A cada uno de estos nodos sin excepción se les pueden seguir agregando n hijos, esto enlazándolos a su ultimo hijo que posee como enlace a su siguiente nodo un nulo. En el caso de la eliminación consta de modificar el enlace de su padre al nodo siguiente de ser el primer hijo que se desea eliminar o re enlazar el puntero del hermano anterior al siguiente del que se desea eliminar si no lo es, claramente se perderán todos los enlaces de la jerarquía del nodo eliminado.
Referencias
vD(2010,31diciembre).IVArboles.Scribbr.es. https://www.cs.upc.edu/~ps/downloads/matdoc/transparencias/ps/ps_IV_arboles.pdf
Torres, D. (2013, 12 abril). estructurasdedatos. utmx. http://www.utm.mx/~dtorres/cursos/estructuradedatos/Tema6-Arboles.pdf
D. (2010, 31 diciembre). IV Arboles. Scribbr.es. https://www.cs.upc.edu/~ps/downloads/matdoc/transparencias/ps/ps_IV_arboles.pdf
Estructuras de Datos y Algoritmos - Arboles digitales: Trie y Patricia. Universidad Nacional de San Luis - 2015
[Salto de ajuste de texto]