Balanceo Arboles Binarios

UNA IMPLEMENTACIÓN MATRICIAL:
Sea A un árbol en el cual los nodos se etiquetan 0,1,2,...,n-1,es decir,cada nodo contiene un campo de información que contendrá estos valores.
La representación más simple de A que soporta la operación PADRE es una matriz lineal P en la cual el valor de P[i] es un valor o un cursor al padre del nodo i.
La raíz de A puede distinguirse dándole un valor nulo o un valor a él mismo como padre.
Por ejemplo.,podemos usar un esquema de cursores donde P[i]=j si el nodo j es el padre del nodo i,y P[i]=-1 (suponemos que NODO_NULO=-1) si el nodo i es la raíz.


IMPLEMENTACIÓN DE ÁRBOLES POR LISTAS DE HIJOS:
Una forma útil e importante de representar árboles es formar para cada nodo una lista de sus hijos.
Las listas pueden representarse por cualquier método,pero como el número de hijos que cada nodo puede tener puede ser variable,las representaciones por listas enlazadas son las más apropiadas.
Hay una matriz de celdas de cabecera indexadas por nodos ,que suponemos numerados 0,1,2,...,n-1.
Cada punto de cabecera apunta a una lista enlazada de elementos que son nodos.
Los elementos sobre una lista encabezada por cabecera[i] son los hijos de i(por ejemplo, 9 y 4 son los hijos de 8).
Si desarrollamos la estructura de datos que necesitamos en términos de un tipo de dato abstracto tLista (de nodos) y damos una implementación particular de listas,puede verse como las abstracciones encajan.
Suponemos que la raíz de cada árbol está almacenada explícitamente en el campo raíz.
El -1 en el campo raíz se usa para representar el árbol nulo o vacío.
Las demás operaciones son también fáciles de implementar utilizando la anterior estructura para el tipo de dato y usando las primitivas del TDA Lista.

Nota:Las funciones PRIMERO,FIN y RECUPERA usadas en el ejemplo anterior pertenecen al TDA Lista anteriormente estudiado

IMPLEMENTACIÓN DE ÁRBOLES BASADA EN CELDAS ENLAZADAS:
Al igual que ocurre en los TDA estudiados (Listas,Pilas o Colas), un nodo puede ser declarado de forma que la estructura del árbol pueda ir en aumento mediante la obtención de memoria de forma dinámica,haciendo una petición de memoria adicional cada vez que se quiere crear un nuevo nodo.
Observemos que bajo esta implementación cada nodo de un árbol contiene 3 punteros:
 1.-Padre que apunta al padre,
 2.-Hizqda que apunta al hijo izquierdo
 3.-Herdrcha que apunta al hermano a la derecha del nodo

Para esta implementación de árbol vamos a presentar las funciones primitivas de las que hablábamos al principio.
Suponemos que para referenciar el nodo i la variable puntero apuntará a ese nodo.
Suponemos también unas variables de tipo nodo y que la variable T de tipo árbol apunta a la raíz del árbol.