我有一个递归函数,可以计算二叉树的节点数,显然它工作正常,但有一件事我不明白。
#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;
}
它是按顺序进行的,你知道,首先是 root,然后访问左孩子,然后是右孩子。问题是,当我一直这样做时,例如,如果我们有这棵树:
它的作用是:
- 它检查树是否为空,因此在第一个函数中,它直接转到 else ,因为树是有根的。
- 递归开始,根、树和计数器被传递给 1(因为它至少有 1 个节点,即根)。
- 我们启动第二个函数,因为它的左子节点是 7 并且它不是空节点,它再次调用 calculateNodos 节点 7、树和 2 处的计数器(我们已经有 1 个根节点和 1 个节点即 7 ,总共 2 个节点)。
- 再次递归调用它,结果它有一个左孩子,它是2并且不是空节点,我们再次调用calculateNodes,节点为2,树,计数器为3(总共3个节点,根, 7 和 2)。
我的疑问来了:
5、再次递归调用,此时节点2既没有左孩子也没有右孩子,即在calculateNodes中,跳过第一个if和第二个if,返回counter。
我的问题是,运行该程序对我来说非常有效,但我不明白的是,如果它在那里返回计数器,程序如何继续计算 7 的右孩子,即 6,但如果它已经返回counter... 也就是说,如果递归已经返回 counter 并完成,递归如何在那里工作,以便它继续读取 7(即 6)的右孩子。
非常感谢。
请注意,当您进行递归调用时,您实际上是在调用另一个函数(尽管在这种特殊情况下,您正在调用的函数是同一个函数)。当您调用的函数返回时,发出调用的函数将在稍后恢复。
因此,第一次
CalculaNodos
从numNodos
传递根(节点2)调用时,后者将等待它CalculaNodos
完成并返回其结果。让我们称之为第一次呼叫call 0 。但是
CalculaNodos
,反过来调用CalculaNodos
它传递节点 7,并等待它的结果。让我们将此第二个呼叫称为呼叫 1。它
CalculaNodos
再次调用CalculaNodos
(call 2)传递它节点 2,并等待结果。在这里,我们终于来了一个不再进行递归调用的调用。根据您的计算,最后一次调用返回 3,但是那个 3 返回给谁呢?谁打来的电话 2。
CalculaNodos
所以当它计算节点 7 的子节点并且已经CalculaNodos
为它的左分支调用了 a 时,我们回到了函数内部。然后它将继续CalculaNodos
为其右分支再次调用 a ,等待相应的结果(稍后将到达几个递归调用)。它将添加每个分支的两个结果并将结果返回给调用者 1,调用者将执行相同的操作,等等。也就是说,递归的好处是当他们返回时,他们不考虑问题已经完成,而只考虑他们正在处理的子问题。请注意,计算分支节点的子问题与计算树节点的最终问题没有什么不同。不同之处在于您处于树的哪个级别以及您将结果返回给谁。