tengo una función recursiva que calcula el numero de nodos que tiene un árbol binario, obviamente funciona bien, pero hay una cosa que no entiendo.
#include <iostream>
#include "abinCeldasEnlazadas.h"
using namespace std;
template <typename T>
int numNodos (const Abin<T>& A)
{
int cont = 0;
if(A.arbolVacioB())
{
return cont;
}
else
{
cont = calculaNodos (A.raizB(), A, 1);
}
return cont;
}
template <typename T>
int calculaNodos (typename Abin<T>::nodo n,const Abin<T>& arbol, int contador)
{
if(arbol.hijoIzqdoB(n) != arbol.NODO_NULO)
{
contador = calculaNodos(arbol.hijoIzqdoB(n),arbol,contador+1);
}
if (arbol.hijoDrchoB(n) != arbol.NODO_NULO)
{
contador = calculaNodos (arbol.hijoDrchoB(n), arbol, contador+1);
}
return contador;
}
Va en preorden, ya sabéis, primero raíz, luego visita hijo izquierdo y luego hijo derecho. La cuestión es que cuando lo he estado realizando, si por ejemplo tenemos este árbol:
Lo que hace es:
- Comprueba que el árbol no está vacío, entonces, en la primera función, se va al else directamente ya que el árbol tiene raíz.
- Empieza la recursividad, se le pasa la raíz, el árbol y el contador a 1 (ya que como mínimo tiene 1 nodo que es el raíz).
- Comenzamos la segunda función, como tiene hijo izquierdo que es 7 y no es un nodo nulo, llama de nuevo a calculaNodos con el nodo 7, el árbol, y el contador a 2 (ya tenemos 1 nodo raíz, y 1 nodo que es 7, en total, 2 nodos).
- Vuelve a llamarse recursivamente, y resulta que vuelve a tener hijo izquierdo, que es el 2 y no es nodo nulo, de nuevo llamamos a calculaNodos con el nodo 2, el árbol, y el contador a 3 (total 3 nodos, raíz, 7 y 2).
AQUÍ VIENE MI DUDA:
5.Se llama recursivamente de nuevo y ya el nodo 2 no tiene ni hijo izquierdo ni hijo derecho, es decir, en calculaNodos, salta el primer if y el segundo if, y devuelve contador.
Mi duda es, funcionar el programa me funciona perfectamente, pero lo que no entiendo es cómo si devuelve ahí contador, el programa sigue contando hijo derecho de 7 que sería el 6, pero si ya antes ha devuelto el contador... Es decir, ¿cómo funciona ahí la recursividad para que siga leyendo el hijo derecho de 7 (que es 6) si ya antes, ha devuelto contador y ha acabado.
Muchas gracias. [1]: https://i.sstatic.net/Jgcnc.png