Skip to main content
Commonmark migration
Origen Enlace

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:

[![Arbol Binario][1]][1]Arbol Binario

Lo que hace es:

  1. 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.
  2. 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).
  3. 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).
  4. 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

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:

[![Arbol Binario][1]][1]

Lo que hace es:

  1. 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.
  2. 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).
  3. 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).
  4. 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

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:

Arbol Binario

Lo que hace es:

  1. 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.
  2. 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).
  3. 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).
  4. 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.

Origen Enlace

Calcular número de nodos de un ABinario

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:

[![Arbol Binario][1]][1]

Lo que hace es:

  1. 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.
  2. 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).
  3. 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).
  4. 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