Arbol

Es un conjunto finito de nodos conectados de forma dinámica de los cuales uno de sus nodos será una raíz y a cada uno de sus elementos pueden seguirle varios elementos de forma no línea, así mismo su estructura puede cambiar durante la ejecución del programa. Un árbol se define como un tipo de grafo que no contiene ciclos.

Así mismo los árboles pueden ser ordenados, donde los subárboles de cada nodo forman un conjunto ordenado, siendo posible distinguir el primer, segundo o último hijo de un nodo particular. O desordenados, donde los subárboles de cada nodo no guardan orden alguno y por ende no existe forma, en este tipo de árboles, de determinar cuál es el primer, segundo o último hijo.

Tipos de arboles

•Árboles binarios: Esta estructura se caracteriza por que cada nodo solo puede tener 0, 1 o 2 hijos como máximo, se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho

•Árbol binario lleno: Es aquel que el que todos los nodos tiene cero o 2 hijos con excepción de la Raíz.

Árbol binario perfecto: Es un árbol lleno en donde todos las Hojas están en el mismo Nivel.

Árbol N-rio: En ellos, el número de hijos que tendrá cada nodo es definido por un valor “N” el cual puede ser definido. 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.

Árbol de expresión: Representan el código de nivel del lenguaje en forma de datos, los datos se almacenan en una estructura con forma de árbol, y cada nodo representa una expresión. Todos los operadores contienen dos operando, mientras que la raíz siempre tendrá que ser un operador.

Elementos

• Nodo (Node): También llamado vértice o elemento del árbol. Es el contenedor de los datos y los enlaces a sus hijos y a su padre.

 • Nodo Raiz (Root Node): Es el nodo donde comienza el árbol. Cada árbol tiene solamente un nodo raíz, desde el cual cuelgan todos sus descendientes.

• Nodo Rama (Branch Node): También llamado nodo interior o interno. Es un nodo cualquiera que puede tener hijos, aunque en este preciso momento no los tenga. Es todo nodo que no es raíz o hoja.

• Nodo Hoja (Leaf Node): También llamado nodo terminal. Es un nodo cualquiera que no puede tener hijos y nunca los podrá tener. Es un nodo que no tiene ningún subárbol.

• Nodo Hermano (Sibling Node): Es un nodo que es hijo del mismo padre.

• Camino (Path): Son los enlaces que van desde un nodo hasta otro nodo.

• Rama (Branch): Es un camino que termina en una hoja.

• Nivel del Nodo (Node Level): Es la longitud del camino desde el nodo raíz al nodo específico más uno.

• Altura del Arbol (Tree Height): También llamado profundidad. Es el número máximo de nodos de una rama del árbol. Es igual al nivel más alto de los nodos del árbol.

• Peso del Arbol (Tree Wheight): Es el número de nodos terminales

• Arbol Vacio (Empty Tree): Es un árbol que en este momento no tiene ningún nodo. De existir solo un nodo, ese nodo es el nodo raíz.

• Grado de un Nodo (Node Degree): Es el número de subárboles que tiene un nodo. Los nodos hoja tienen grado cero.

• Grado de un Arbol (Tree Degree): El grado máximo de todos los nodos del árbol.

• Ancestros del Nodo (Ancestors): Son todos los nodos del árbol en el camino que va desde la raíz hasta el nodo específico.

Operaciones Básicas

• Insertar elemento: Permite insertar un elemento en un nodo del árbol.

• Buscar: Permite localizar elementos en cualquier parte del árbol.

• Eliminar elemento: Permite eliminar un elemento en un punto específico del árbol.

• Ir a la raíz: Redirige hasta la raíz de un árbol.

• Recorrer: Los recorridos son algoritmos que nos permiten recorrer un árbol en un orden específico, los recorridos nos pueden ayudar encontrar un nodo en el árbol, o buscar una posición determinada para insertar o eliminar un nodo. Estos recorridos pueden ser: pre-orden (raíz > hijo izquierdo > hijo derecho), in-orden (hijo izquierdo > raíz > hijo derecho), post-orden (hijo izquierdo > hijo derecho > raiz) ó por niveles (recorre todos los nodos de un nivel de izquierda a derecha y luego pasa al siguiente nivel).