1

我对以下查找树的高度的代码和递归查找的代码有点困惑sum of n nos，这在下面。lheight和存储什么rheight，取决于它进行的递归次数？

int height(struct node* node)
{
   if (node==NULL)
       return 0;
   else
   {
     lheight = height(node->left);
     rheight = height(node->right);
     if (lheight > rheight)
         return(lheight+1);
     else return(rheight+1);     
   }
}

这是一个更澄清，它打印的总和n nos：

int findSum(int n){
    int sum;
    if(n <= 0) return 0;
    else sum = n + findSum(n-1);
    return sum;
}

如果我将其更改为：

int findSum(int n){
    int sum;
    if(n <= 0) return 0;
    else sum = findSum(n-1); // here
    return sum;
}

它将输出打印为 0。如果上面的树代码返回，为什么不返回递归数？

4

3 回答 3

3

您的第二次递归相当于

sum = findSum(n-1) = findSum(n-2) = findSum(n-3) = ..... = findSum(0) = 0;

如果您希望第二次递归返回递归次数，请使用

sum = 1 + findSum(n-1);

和返回树级别lheight，rheight因为在递归函数中1，两个变量都有增量：

     return(lheight+1);
 else return(rheight+1);

如果你想让你findsum()做和你的height()recurssion 一样的事情，你应该返回sum+1而不是sum在你的findsum()函数结束时：

int findSum(int n){
    int sum;
    if(n <= 0) return 0;
    else sum = findSum(n-1);
    return sum+1; //<<<<< should return sum +1 as you did in the height function
}

return sum+1;只有当

findSum(n-1); findSum(n-2); findSum(n-3); ... findSum(0); 被称为。

  • 当findSum(0)被调用时，它将返回0；
  • 当findSum(1)被调用时，它会执行sum=findSum(0)(so sum = 0)然后返回sum+1( 1)；
  • 当findSum(2)被调用时，它会执行sum=findSum(1)(so sum = 1)然后返回sum+1( 2)；
  • 当findSum(3)被调用时，它会执行sum=findSum(2)(so sum = 2)然后返回sum+1( 3)；
  • .
  • .
  • .
  • 当findSum(n)被调用时，它会执行sum=findSum(n-1)(so sum = n-1)然后返回sum+1( n)；
于 2013-05-21T08:03:50.517 回答
1

我建议你在纸上这样做。如果我们为（未修改的）findSum函数这样做，它将是这样的：

免得说你这样称呼它

findSum(2);

这将阅读以下步骤：

1: sum = 2 + findSum(2 - 1);

哪个会调用findSum(1)哪个导致

2: sum = 1 + findSum(1 - 1);

哪个调用findSum(0)哪个是

3: return 0;

现在我们回退一步2：

2: sum = 1 + 0;

并再次备份：

1: sum = 2 + 1

所以结果findSum(2)是 3。

于 2013-05-21T08:07:56.580 回答
1

lheight 和 rheight 只不过是左子树和右子树在树的特定级别上的高度。

如果您举一个例子，这可以更容易理解。 树

在附图中，我们从根 F 开始。我们检查根是否为空，如果它不是，我们找到右子树和左子树的高度，取其多，我们再加一个它并返回。这就是我们手动操作的方式。

现在在找到左子树的高度时，我们递归地向下，直到我们到达一个空指针，此时我们返回0。因此A的返回值是0，然后我们检查右子树的高度（即D) 并且为此我们递归地向下直到C，为此返回0，同样为0返回0。我们将C和E的最大值加1（即0）并将其返回到上层。现在我们的 A 值为 0，D 值为 1，我们将最大值加 1（即 1）并将其返回到上层。这是完整树的左子树的高度，同样计算右子树的高度。

于 2013-05-21T08:09:40.590 回答