arboles en c

Implementación en C
Un árbol binario puede declararse de varias maneras. Algunas de ellas son:
Estructura con manejo de memoria dinámica, siendo puntA el puntero que apunta al árbol de tipo tArbol:
typedef struct nodo {
int clave;
struct nodo *izdo, *dcho;
}Nodo;
Estructura con arreglo indexado:
typedef struct tArbol
{
int clave;
tArbol hIzquierdo, hDerecho;
} tArbol;tArbol árbol[NUMERO_DE_NODOS];
En el caso de un árbol binario casi-completo (o un árbol completo), puede utilizarse un sencillo arreglo de enteros con tantas posiciones como nodos deba tener el árbol. La información de la ubicación del nodo en el árbol es implícita a cada posición del arreglo. Así, si un nodo está en la posición i, sus hijos se encuentran en las posiciones 2i+1 y 2i+2, mientras quesu padre (si tiene), se encuentra en la posicióntruncamiento((i-1)/2) (suponiendo que la raíz está en la posición cero). Este método se beneficia de un almacenamiento más compacto y una mejor localidad de referencia, particularmente durante un recorrido en preorden. La estructura para este caso sería por tanto:
int árbol[NUMERO_DE_NODOS];
[editar]Recorridos sobre árboles binarios[editar]Recorridos en profundidad
El método de este recorrido es tratar de encontrar de la cabecera a la raíz en nodo de unidad binaria. Ahora pasamos a ver la implementación de los distintos recorridos:
[editar]Recorrido en preorden
En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata elsubárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.
En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.
void preorden(tArbol *a)
{
if (a != NULL) {
tratar(a); //Realiza una operación en nodopreorden(a->hIzquierdo);
preorden(a->hDerecho);
}
}
Implementación en pseudocódigo de forma iterativa:
push(s,NULL); //insertamos en una pila (stack) el valor NULL, para asegurarnos de que esté vacía
push(s,raíz); //insertamos el nodo raíz
MIENTRAS (s NULL) HACER
p = pop(s); //sacamos un elemento de la pila
tratar(p);//realizamos operaciones sobre el nodo p
SI (D(p) NULL) //preguntamos si p tiene árbol derecho
ENTONCES push(s,D(p));
FIN-SI
SI (I(p) NULL) //preguntamos si p tiene árbol izquierdo
ENTONCES push(s,I(p));
FIN-SI
FIN-MIENTRAS
[editar]Recorrido en postorden
En este caso se trata primero el subárbol izquierdo, despuésel derecho y por último el nodo actual. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda, nodo derecha, nodo raiz. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.
void postorden(tArbol *a)
{
if (a != NULL) {
postorden(a->hIzquiedo);
postorden(a->hDerecho);
tratar(a);//Realiza una operación en nodo
}
}
[editar]Recorrido en inorden
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda,nodo raiz,nodo derecha. En el árbol de la figura elrecorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4, 9.
Esquema de implementación:
void inorden(tArbol *a)
{
if (a != NULL) {
inorden(a->hIzquierdo);
tratar(a); //Realiza una operación en nodo
inorden(a->hDerecho);
}
}
[editar]Recorridos en amplitud (o por niveles)
En este caso el recorrido se realiza en orden por los distintos niveles...