Estructuras No Lineales

4 ESTRUCTURA NO LINEALES

4.1 arboles

En ciencias de la informática, un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Unnodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso,también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.

Formalmente, podemos definir un árbol de lasiguiente forma recursiva:

▪ Caso base: 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 [pic]de raíces [pic]con [pic]elementos cadauno, 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 [pic]nodos tiene como raíz el nodo nr, los nodos [pic]son loshijos de nr y el conjunto de nodos hoja está formado por la unión de los k conjuntos hojas iníciales. A cada uno de los árboles Ai se les denota ahora subárbols 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 en anchura. 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 elsiguiente 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. Otrosrecorridos típicos del árbol son:

▪ 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 [pic]en orden previo.
▪ El...