Arboles y arboles binarios

DEFINICION ARBOL
En ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo 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 eshijo 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. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.
Formalmente, podemos definir un árbol de la siguiente forma:
* 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 deraí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.
Unasucesió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 nodoanterior 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 pre orden, post orden e in orden:
* El recorrido en pre orden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luegocada uno de los hijos en orden previo.
* El recorrido en in orden, 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 orden simétrico.
* El recorrido en post orden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos enorden posterior y por último la raíz.

ÁRBOL BINARIO
Un árbol binario como lo indica su nombre, estos árboles están formados por nodos que pueden tener un máximo de 2 hijos, con raíz es un árbol T con un vértice distinguido al que se denomina raíz. Este vértice se representa encima de los restantes, que se colocan por niveles según su distancia a la raíz. Se llama altura (o profundidad) de unárbol con raíz a la máxima distancia de un vértice a la raíz. Para cada vértice u, que no sea la raíz, se llama padre de u al único vértice adyacente a u que se encuentra en el camino de u a la raíz. Se llaman hijos de u a los restantes vértices adyacentes, (que se encuentran por debajo de u).
Los vértices sin hijos son las hojas del árbol, y los vértices que no son hojas ni raíz se denominanvértices interiores.
La altura de un árbol binario es el nivel máximo de sus hojas (también se conoce a veces como la profundidad del árbol). Por conveniencia, la altura del árbol nulo se define como –1.
Si un árbol binario tiene una altura k, entonces hay un nodo en el nivel k (el nodo raíz), dos nodos en el nivel k-1, 4 en el nivel k-2 y así sucesivamente; habrá 2k-1, y al menos 1 y no más de 2ken el nivel 0. Si el árbol contiene n nodos en total, contando tanto los nodos internos como las hojas se llega a que 2k < n < 2k-1. De igual forma la altura de un árbol que contenga n nodos es:
k = | log n |

 
Un árbol binario balanceado (a veces llamado árbol AVL) Es un árbol binario en el cual las alturas de los subárboles de todo nodo difieren a los sumo en 1. El balance de un nodo...