1

.1.1. Definición y conceptos básicos
Los árboles se pueden definir como un tipo restringido de grafo. 
Un grafo se define de la siguiente manera: Un grafo consiste de un número de nodos (puntos o vértices) y un grupo de arcos que unen parejas de nodos. A todos los pares de nodos unidos por un arco se les llama nodos adyacentes. Los arcos pueden tener una dirección determinada, generando así ungrafo dirigido, el cual de lo contrario sería no-dirigido. (También existen los grafos mixtos).
Por convención a los nodos de un grafo se le representa con círculos y los arcos que los conectan como líneas(no-dirigido) o flechas (dirigido).
Los árboles son entonces un subconjunto importante de los grafos, y son una herramienta útil para describir estructuras que representan algún tipo dejerarquía.
Un árbol dirigido tiene un nodo al que se le llama "raíz" y de este nodo parten todas las conexiones a los demás nodos. A los nodos terminales se les llama "hojas" y a todos los demás se les llama nodos intermedios.
De acuerdo al número de arcos que parten de cada nodo en un árbol, este se puede clasificar en diferentes categorías. A los nodos que dependen de otro nodo también se les conocecomo nodos "hijos" o descendientes y al otro se le llama nodo "padre".
De esto de puede concluir que cada nodo padre es una raíz de un sub-árbol. El número de sub-árboles que tiene un nodo determinan el grado del nodo. Naturalmente el grado de las hojas es de cero. Por convención al nodo raíz de árbol se le considera el nivel cero del árbol.
Cuando se tienen varios árboles en un conjunto, alconjunto se le llama bosque.
Altura de un nodo: Es la longitud del camino más largo desde el nodo hasta una hoja que sea descendiente de este nodo.
Altura de un árbol = altura del nodo raíz. 











4.1.2 Arboles binarios; representación

Recorrido de arboles binarios: In-order, Pre-order, Pos-order. Algoritmos e implementación.
Árboles binarios 
Un árbol binario es representado con nodos ligados:Como lo indica su nombre, estos árboles están formados por nodos que pueden tener un máximo de 2 hijos.

DEFINICIONES :
Árbol relleno : Cuando todo nodo tiene 2 hijos o bien es hoja. 
Árbol binario completo : Un árbol binario relleno en dónde todas las hojas tienen la misma profundidad.
Métodos para recorrer un árbol binario:
RECORRIDO PRE-ORDER:
1. visitar el raíz
2. ir a subárbol izquierdo
3. ira subárbol derecho
Camino: A,B,D,E,C,F Y G

RECORRIDO IN-ORDER
1. recorrer subárbol izquierdo
2. visitar el raíz
3. ir a subárbol derecho
CAMINO: D,B,E,A,F,C Y G

RECORRIDO POST-ORDER
1. ir a subárbol izquierdo
2. ir a subárbol derecho 
3. visitar raíz
CAMINO: D,E,B,F,G,C Y A

Intercambiando izquierda por derecha en los tres métodos anteriores se obtienen tres métodos a los cuales se les llama: 
1. Pre-order converso 
2. En-order converso 
3. Post-order converso 
Observando el ejemplo de la figura:

Recorriendo a este árbol con en los diferentes métodos se obtendrían las siguientes cadenas :
pre-order : 32 1 5 1 8 11 17 23 56 43 41 53 72 64 80
en-order : 1 5 8 1 17 11 23 32 41 43 53 56 64 72 80
post-order : 1 8 5 17 23 11 1 41 53 43 64 80 72 56 32
Alta en un árbol binario: 
Parafacilitar el proceso cada nodo tiene una liga adicional que apunta a su predecesor: nodo->padre.
#include 
#include 
#include 
void alta(struct nodo *raiz, int dato);
void baja(struct nodo *p, int dato);
void imprime_arbol(struct nodo *raiz, int i);
struct nodo *sucesor(struct nodo *p);
struct nodo *busca_nodo(struct nodo *p, int dato)
struct nodo{ 
int clave;
struct nodo *padre;
struct nodo *izq,*der;
};
void main(void)
{
char mov = 'a',c;
struct nodo *raiz;
int dato;
raiz = (struct nodo *) malloc(sizeof(struct nodo));
raiz->clave = -1;
raiz->izq = NULL;
raiz->der = NULL;
raiz->padre = NULL;
while(mov != 'f') 
{
printf("\n Alta, Baja o Fin ? :");
mov = getchar();
c = getchar();
switch(mov)
{
case 'a': printf("\n Dato a dar de alta:");
scanf("%d", &dato);
c = getchar();
alta(raiz, dato);...