Perro

Árboles
Arboles binarios
En Programación, Un árbol binario es una estructura de datos en donde cada nodo, o elemento, tiene un hijo izquierdo y un hijo derecho. Si un nodo no tiene hijos, entonces es null o que no guarda ningún dato. Esto se le conoce como un nodo externo.
La idea de los arboles binarios es para guardar datos que están directamente relacionados. Cada hijo de un nodoprincipal puede guardar tener otros hijos. Existen arboles binarios completos y casi completos. Los completos tienen sus elementos finales a la misma profundidad, siendo así de una manera simétrica, y los casi completos son lo opuesto. Los elementos finales de una rama no están a la misma profundidad que los de la otra rama.

Recorridos de Árboles Binarios
Recorrido en Preorden
Se recorrerá cadaelemento en la rama izquierda, y al terminar en la derecha. El recorrido sigue el orden: nodo raíz, nodo izquierdo, nodo derecho… En la imagen superior, tomando como base el árbol binario completo, el recorrido sería: A, B, D, E, H, I, A, C, F, G, J, K.
void preorden(tArbol *a)
{
if (a != NULL) {
tratar(a); //Realiza una operación en nodo
preorden(a->hIzquierdo);preorden(a->hDerecho);
}
}



Recorrido en Postorden
Básicamente, es lo opuesto que el recorrido en preorden. Empieza con la rama izquierda, pero empieza con el nodo izquierdo y termina con el nodo raíz. En el ejemplo, el recorrido seria: H, D, I, E, B, K, J, F, C, G, A.
void postorden(tArbol *a)
{
if (a != NULL) {
postorden(a->hIzquiedo);
postorden(a->hDerecho);tratar(a); //Realiza una operación en nodo
}
}

Recorrido Inorden
El recorrido empieza en el nodo izquierdo, luego va al nodo principal y termina en el nodo derecho.
void inorden(tArbol *a)
{
if (a != NULL) {
inorden(a->hIzquierdo);
tratar(a); //Realiza una operación en nodo
inorden(a->hDerecho);
}
}

Recorridopor Niveles
El recorrido va por los niveles diferentes del árbol, empezando por el nivel superior leyendo de izquierda a derecha. En la imagen, el recorrido sería: A, B, C, D, E, F, G, H, I, J, K.
void arbol_recorrido_anch (tipo_Arbol* A) {
tipo_Cola cola_nodos; // esta cola esta implementada previamente, almacena punteros (posiciones de nodos de árbol)

tipo_Pos nodo_actual; //este es un puntero llevara el recorrido

if (vacio(A)) // si el árbol esta vacio, salimos
return;

cola_inicializa(&cola_nodos); // obvio, y necesario

cola_enqueue(A, &cola_nodos); // se encola la raiz

while (!vacia(&cola_nodos)) { // mientras la cola no se vacie se realizara el recorrido
nodo_actual = cola_dequeue(&cola_nodos) // de la cola saldran losnodos ordenados por nivel

printf("%c,", nodo_actual->info); // se "procesa" el nodo donde va el recorrido, en este caso se imprime

if (nodo_actual->izq != null) // si existe, ponemos el hijo izquierdo en la cola
cola_enqueue(nodo_actual->izq, &cola_nodos);

if (nodo_actual->der != null) // si existe, ponemos el hijo derecho en la colacola_enqueue(nodo_actual->der, &cola_nodos);

} // al vaciarse la cola se han visitado todos los nodos del árbol
}

Árbol Binario de Búsqueda
Todo árbol vacío es un árbol binario de búsqueda.

Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
• En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo
almacenado en el subárbolizquierdo, y que el subárbol izquierdo sea un árbol binario
de búsqueda.
• En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo
almacenado en el subárbol derecho, y que el subárbol derecho sea un árbol binario
de búsqueda.

Con un árbol binario de búsqueda, se pueden hacer varias operaciones, entre ellas la inserción y supresión de nodos.

Inserción de...