Tipos de arboles

ÁRBOL CONCEPTOS, RECORRIDOS, ALGORITMOS
Definición: es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos, un árbol es una estructura en compuesta por un dato y varios árboles.
Conceptos en relación con otros nodos:
* 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 quecontiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.
En cuanto a la posición dentro del árbol:
Nodo raíz: nodo que no tiene padre.
Nodo hoja: nodo que no tiene hijos.
Nodo rama: son los nodos que no pertenecen a ninguna de las dos categorías anteriores.
Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbolcompleto.

Otros conceptos que definen las características del árbol, en relación a su tamaño:
Orden: es el número potencial de hijos que puede tener cada elemento de árbol.
Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol.
Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno.Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel.
Ejemplo de nodo para crear árboles de orden tres:
struct nodo {
int dato;
struct nodo *rama1;
struct nodo *rama2;
struct nodo *rama3;
};
O generalizando más:
#define ORDEN 5

struct nodo {
int dato;
struct nodo *rama[ORDEN];
};

Declaraciones de tipos para manejar árboles en C
typedefstruct _nodo {
int dato;
struct _nodo *rama[ORDEN];
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Arbol;
Declaramos un tipo tipoNodo para declarar nodos, y un tipo pNodo para es el tipo para declarar punteros a un nodo.
Arbol es el tipo para declarar árboles de orden ORDEN.

Operaciones básicas con árboles
Salvo que trabajáramos con árboles especiales, las insercionesserán siempre en punteros de nodos hoja o en punteros libres de nodos rama.
* Añadir o insertar elementos.
* Buscar o localizar elementos.
* Borrar elementos.
* Moverse a través del árbol.
* Recorrer el árbol completo.
Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que estemos implementando.
Recorridos por árboles
El modo evidente de moverse através de las ramas de un árbol es siguiendo los punteros, Esos recorridos dependen en gran medida del tipo y propósito del árbol.
Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una.
Ejemplo: Supongamos que tenemos un árbol de orden tres, y queremos recorrerlo porcompleto.
Partiremos del nodo raíz:
RecorrerArbol(raiz);
La función RecorrerArbol, aplicando recursividad, será tan sencilla como invocar de nuevo a la función RecorrerArbol para cada una de las ramas:
void RecorrerArbol(Arbol a) {
if(a == NULL) return;
RecorrerArbol(a->rama[0]);
RecorrerArbol(a->rama[1]);
RecorrerArbol(a->rama[2]);
}
Lo que diferencia los distintosmétodos de recorrer el árbol no es el sistema de hacerlo, sino el momento que elegimos para procesar el valor de cada nodo con relación a los recorridos de cada una de las ramas.

Los tres tipos son:
Pre-orden
el valor del nodo se procesa antes de recorrer las ramas:
void PreOrden(Arbol a) {
if(a == NULL) return;
Procesar(dato);
RecorrerArbol(a->rama[0]);RecorrerArbol(a->rama[1]);
RecorrerArbol(a->rama[2]);
}
In-orden
el valor del nodo se procesa después de recorrer la primera rama y antes de recorrer la última. Esto tiene más sentido en el caso de árboles binarios, y también cuando existen ORDEN-1 datos, en cuyo caso procesaremos cada dato entre el recorrido de cada dos ramas (este es el caso de los árboles-b):
void InOrden(Arbol a) {
if(a ==...