Información:
Comprobar si un árbol está vacío.
Calcular el número de nodos.
Comprobar si el nodo es hoja.
Calcular la altura de un nodo.
Calcular la altura de un árbol.
Hay varios parámetros que podemos calcular o medir dentro de un árbol. Algunos de ellos nos darán idea de lo eficientemente que está organizado o el modo en que funciona.
Un árbol está vacío si su raíz es NULL.
Tenemos dos opciones para hacer esto, una es llevar siempre la cuenta de nodos en el árbol al mismo tiempo que se añaden o eliminan elementos. La otra es, sencillamente, contarlos.
Para contar los nodos podemos recurrir a cualquiera de los tres modos de recorrer el árbol: inorden, preorden o postorden, como acción sencillamente incrementamos el contador.
Esto es muy sencillo, basta con comprobar si tanto el árbol izquierdo como el derecho están vacíos. Si ambos lo están, se trata de un nodo hoja.
No hay un modo directo de hacer esto, ya que no nos es posible recorrer el árbol en la dirección de la raíz. De modo que tendremos que recurrir a otra técnica para calcular la altura.
Lo que haremos es buscar el elemento del nodo de que queremos averiguar la altura. Cada vez que avancemos un nodo incrementamos la variable que contendrá la altura del nodo.
Empezamos con el nodo raíz apuntando a Raiz, y la 'Altura' igual a cero.
Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda y el valor de la altura es 'Altura'.
Incrementamos 'Altura'.
Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.
Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.
La altura del árbol es la altura del nodo de mayor altura. Para buscar este valor tendremos que recorrer todo el árbol, de nuevo es indiferente el tipo de recorrido que hagamos, cada vez que cambiemos de nivel incrementamos la variable que contiene la altura del nodo actual, cuando lleguemos a un nodo hoja compararemos su altura con la variable que contiene la altura del árbol si es mayor, actualizamos la altura del árbol.
Iniciamos un recorrido del árbol en postorden, con la variable de altura igual a cero.
Cada vez que empecemos a recorrer una nueva rama, incrementamos la altura para ese nodo.
Después de procesar las dos ramas, verificamos si la altura del nodo es mayor que la variable que almacena la altura actual del árbol, si es así, actualizamos esa variable.
Esta función es fácil de implementar:
int Vacio(Arbol r) {
return r==NULL;
}
Esta función también es sencilla de implementar:
int EsHoja(pNodo r) {
return !r->derecho && !r->izquierdo;
}
En el punto 7.7 comentábamos que para contar los nodos podemos recurrir a cualquiera de los tres modos de recorrer el árbol: inorden, preorden o postorden y como acción incrementamos el contador de nodos. Para implementar este algoritmo recurrimos a dos funciones:
int NumeroNodos(Arbol a, int *contador) {
*contador = 0;
auxContador(a, contador);
return *contador;
}
void auxContador(Arbol nodo, int *c) {
(*c)++; /* Acción: incrementar número de nodos. (Preorden) */
if(nodo->izquierdo) auxContador(nodo->izquierdo, c); /* Rama izquierda */
if(nodo->derecho) auxContador(nodo->derecho, c); /* Rama derecha */
}
Es un problema parecido al anterior, pero ahora tenemos que contar la altura, no en número de nodos. Cada vez que lleguemos a un nodo hoja, verificamos si la altura del nodo es la máxima, y si lo es, actualizamos la altura del árbol a ese valor:
Iniciamos un recorrido del árbol en postorden, con la variable de altura igual a cero.
Cada vez que empecemos a recorrer una nueva rama, incrementamos la altura para ese nodo.
Después de procesar las dos ramas, verificamos si la altura del nodo es mayor que la variable que almacena la altura actual del árbol, si es así, actualizamos esa variable.
int AlturaArbol(Arbol a, int *altura) {
*altura = 0; /* (1) */
auxAltura(a, 0, altura);
return *altura;
}
void auxAltura(pNodo nodo, int a, int *altura) {
/* (2) Cada vez que llamamos a auxAltura pasamos como parámetro a+1 */
if(nodo->izquierdo) auxAltura(nodo->izquierdo, a+1, altura); /* Rama izquierda */
if(nodo->derecho) auxAltura(nodo->derecho, a+1, altura); /* Rama derecha */
if(EsHoja(nodo) && a > *altura) *altura = a; /* Proceso (Postorden) (3) */
}
Lo que haremos será buscar el elemento del nodo del que queremos averiguar la altura. Cada vez que avancemos un nodo incrementamos la variable que contendrá la altura del nodo.
Empezamos con el nodo raíz apuntando a Raiz, y la 'Altura' igual a cero.
Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda y el valor de la altura es 'Altura'.
Incrementamos 'Altura'.
Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.
Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.
int Altura(Arbol a, int dat) {
int altura = 0;
pNodo actual = a; /* (1) */
while(!Vacio(actual)) {
if(dat == actual->dato) return altura; /* dato encontrado. (2) */
else {
altura++; /* (3) */
if(dat < actual->dato) actual = actual->izquierdo; /* (4) */
else if(dat > actual->dato) actual = actual->derecho; /* (5) */
}
}
return -1; /* No está en árbol */
}