Arboles

Árboles
Un árbol dirigido es una estructura:
Jerárquica: porque los componentes están a distinto nivel.
Organizada: porque importa la forma en que esté dispuesto el contenido.
Dinámica: porque su forma, tamaño y contenido pueden variar durante la ejecución.
Un árbol puede ser: vacío, Una raíz + subárboles.
Formalmente, podemos definir un árbol de la siguiente forma:
• Casobase: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
• Un nuevo árbol a partir de un nodo nr y k árboles de raíces con elementos cada uno, puede construirse estableciendo una relación padre-hijo entre nr y cada una de las raíces de los k árboles.
El árbol resultante de nodos tiene como raíz el nodo nr, los nodos son los hijos de nr y el conjunto de nodos hoja estáformado por la unión de los k conjuntos hojas iniciales. A cada uno de los árboles Ai se les denota ahora subárboles de la raíz.
Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol.
Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero enanchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel n + 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden,postorden e inorden:
• El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos en orden previo.

• El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A1, luego la raíz y luego cada uno de los hijos en ordensimétrico.
• El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos en orden posterior y por último la raíz.
Finalmente, puede decirse que esta estructura es una representación del concepto de árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico.
Características generales de un árbol



Los árboles constan denodos, estos son un punto de intersección o unión de varios elementos que confluyen en el mismo lugar. Un nodo puede ser de varios tipos:
• Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
• Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.
Los árboles con los quetrabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.
En cuanto a la posición dentro del árbol, el nodo puede ser:
• Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos parareferirnos al árbol. En el ejemplo, ese nodo es el 'A'.
• Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
• Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.
Otra característica que normalmente tendrán nuestros árboleses que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos. Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada...