Algoritmos recursivos sobre árboles
Los árboles, siendo estructuras recursivas, se prestan muy naturalmente para ser procesados por algoritmo recursivos. Uno de los más fáciles de entender es el recorido In-Order.
void InOrder(BTNode *r) {
if (r) {
InOrder(r->left);
cout << r->data << endl;
InOrder(r->right);
}
}
Ilustramos la ejecución de InOrder en la siguiente animación (puedes dar click para avanzar)
El algoritmo InOrder se considera un recorrido en profundidad. Otras variantes de ese recorrido son los algoritmos PreOrder y PostOrder.
void PreOrder(BTNode *r) {
if (r) {
cout << r->data << endl;
PreOrder(r->left);
PreOrder(r->right);
}
}
El orden de impresión usando PreOrder para el grafo que estamos estudiando es:
56, 13, 32, 23, 22, 15, 31, 48, 87
void PostOrder(BTNode *r) {
if (r) {
PostOrder(r->left);
PostOrder(r->right);
cout << r->data << endl;
}
}
El orden de impresión usando PostOrder para el grafo que estamos estudiando es:
15, 22, 31, 23, 48, 32, 13, 87, 56
Si nos queremos poner creativos podemos seguir inventando algoritmos de recorrido en profundidad como este:
void SomeOrder(BTNode *r) {
if (r) {
cout << r->data << endl;
SomeOrder(r->right);
SomeOrder(r->left);
}
}
¿En que orden se imprimirían si usamos un recorrido SomeOrder?
Algoritmos recursivos sobre árboles
La mayoría de las veces en que necesitamos resolver un problema de BSTs que requiere considerar todos sus nodos, la forma más natural de resolver es usando un algoritmo recursivo. Por ejemplo, digamos que deseamos determinar la suma de todos los nodos de un BST. Si vamos a resolver ese problema usando un algoritmo recursivo debemos pensar en al menos un caso base y caso recursivo.
Caso(s) base
Al procesar árboles, la mayoría de las veces el caso base es uno de dos: (a) el caso nulo o (b) el caso cuando el nodo que estamos visitando es una hoja. En los algoritmos de recorrido que acabas de estudiar, el casobase está implícito en el if (r) pues está diciendo cuando el nodo sea NULL, no hagas nada. Para un algoritmo como el de suma, que desea devolver un valor, no es suficiente hacer nada, i.e. hay que devolver algo. En el caso de un algoritmo que sumará los valores de los nodos, lo más lógico sería que en presencia de un nodo NULO devolvamos el valor 0. En otras palabras sum(NULL) = 0.
El caso recursivo
Para el caso recursivo recomiendo que te imagines que se está invocando la función sobre un nodo n para el que (mágicamente) ya conoces el resultado de la suma de su sub-árbol izquierdo y la suma de su sub-árbol derecho. Entonces te planteas lo siguiente: ¿cómo expresarías la suma total del árbol basado en el nodo n?
En este caso, podrías expresar la suma como sum(n) = n + sum(n->left) + sum(n->right).
int sum(BTNode *n) {
if (!n) return 0;
else return n->data + sum(n->left) + sum(n->right);
}
Otros ejemplos
Función para devolver la cantidad de hojas de un BST.
Casos base: Si el nodo es NULL devolver 0. Si el nodo que estamos visitando es una hoja, devolver 1. Caso recursivo: Si conocemos el número de hojas del sub-arbol izquierdo y del sub-arbol derecho, devolvemos la suma de ambos.
int leafQty(BTNode *n) {
if (!n) return 0;
if (!n->left and !n->right) return 1;
return leafQty(n->left) + leafQty(n->right);
}
Función para determina cuántos nodos internos tienen dos hijos
Casos bases: Si el nodo que estamos visitando es una hoja, devolver 0. Si es NULO, devolver 0. Caso recursivo: Si el nodo que estamos visitando tiene un solo hijo, devolver la cantidad de nodos de dos hijos que tenga su subárbol. Si el nodo que estamos visitando tienen dos hijos, devolver 1 + la suma de los nodos de hijos que tengan sus subárboles.
int parentsOfTwo(BTNode *n) {
if (!n || (!n->left && !n->right)) return 0;
int resultLeft = parentsOfTwo(n->left);
int resultRight = parentsOfTwo(n->right);
if (n->left && n->right) return 1 + resultLeft + resultRight;
else return resultLeft + resultRight;
}
Ejercicios
Añade los siguientes member functions a la clase BST:
int height(BTNode *n) const: devuleve la altura del árbol.int innerNodes(BTNode *n) const: devuelve la cantidad de nodos internos (aquellos que no son hojas y que no son la raíz).int range() const: devuelve la diferencia entre el elemento máximo y el mínimo del arbol. Este algoritmo se puede hacer en O(height) y no requiere recursión.