El árbol binario, en ciencias de la computación

Definición:

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

Ejemplo:

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 el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este método seria seguir el orden: nodo raíz, 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 nodo

preorden(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

Recorrido en postorden

En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este método seria seguir el orden: nodo izquierda, nodo derecha, nodo raíz. 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

}

}

Recorrido en enorden

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

...