在c中解释“int”类型递归函数的返回值

Question

无法理解如何使用int类型的递归函数查找二叉查找树的高度的解释。

对于任何二元搜索树，给定一个指向树的根节点的指针，其中节点按常规定义如下。。。

struct Node {
    int data;
    Node* left;
    Node* right;
}
Node* root;

我们可以使用以下int类型的递归函数来给出二元搜索树的高度。。。（函数“max”只取两个整数，并返回其中较大的一个）

int findHeight(Node* root){
    if(root == NULL){
        return -1;
    }
    return max(findHeight(root->left),findHeight(root->right)) + 1;
}

int max(int a, int b){
    if (a > b)
        return a;
    else
        return b;
}

我的理解是findHeight（根-

我对递归非常陌生，所以我决定只解压缩其中一个递归函数调用，并尝试理解它。我写了findHeight（根-

int fH(Node* root){
    if(root == NULL)
        return -1;

    fH(root->left);
    PAUSE

    int fH(Node* root){
        if root == NULL)
            return -1;

        fH(root->left);
        PAUSE

        int fHR(Node*root){
            if (root == NULL)
                return -1;

            fH(root->left);
            PAUSE

            int fHR(Node* root){
                if (root == NULL)
                    return -1;

                fH(root->left);
                PAUSE

                int fHR(Node* root){
                if(root==NULL)
                    return -1;
                }
            }
        }
    }
}

该函数工作正常，但我不理解函数的返回值是如何从函数的最终执行返回的-1增长到2的。递归int函数是否每次返回到前一个堆栈帧时，都会向其返回值添加1？

我在这个短函数中没有看到任何增加函数返回值的内容。我看到的唯一一件事是最后一个电话是-1。

如果有人能向我解释这一点，我将非常感谢你的帮助。非常感谢你。

Answer 1

我对您的问题的理解是，findHeight的每个递归调用的高度是如何递增的，如果不完全正确，请告诉我。

一般来说，在C语言中，没有特定的语法将函数定义为递归函数，而是由程序员通过其函数的参数和返回值递归使用其函数。

使用此特定函数，增量似乎发生在此行的末尾：

    return findHeight(max(findHeight(root->left),findHeight(root->right)) + 1;

返回函数末尾的1显式递增递归调用，除了返回int之外，int函数没有执行任何隐式递增。

Answer 2

想想这棵树，

     5
   /   \
  3     10
 / \   /  
2   4 8

该函数将使用root调用，root为5。

然后，它将被调用为3、2（左子级）和4（右子级）。

2的高度计算为max（-1，-1）1=0，并作为3调用findHeight（root）的结果返回-

调用3（5'sfindHeight（根-

因此，左孩子的身高为1。

另一个子项（右子项）遵循相同的过程，其中对左子项的调用返回高度为0，而右子项返回高度为1max（0，-1）1=1，它将返回到对findHeight（root）的调用-

现在回到顶部，5的高度被评估为最大（1,1）1=2。

Answer 3

函数findHeight返回当前找到的最大高度。

所以考虑到这一点，最大通话是合理的。

在这个动作重演中，我们得到以下函数调用。

1. 调用节点1。我们希望在左手边再找到2个深度。右手边还有一个。因此，马克斯很可能会选择左手边。max调用Node2和node3
2. 第4点讨论了对2的调用
3. 对3的调用返回0。最大值为-1和-1，1。最大值为-1，再加一个
4. 节点2的findHeight最大值为（左节点（-1）），右节点4）项为5 1
5. 最大值为-1，-1 1=0。这使得第4点的最大值为1

最后，函数findHeight说，这是我当前检查的结束（0高度）。前面的函数调用可以在我的函数中添加任何他们喜欢的内容。

在我看来，这个函数可以用更直观的方式编写。

也许吧

int treeHeight(Node* node){
    if (!node) // We are not a node.
        return 0;
    int weAreANode = 1;  // Height 1.
    int heightLeft = treeHeight(node->left);
    int heightRight = treeHeight(node->right);
    int theHighestSubtreeHeight = std::max(heightLeft, heightRight);

    return weAreANode + theHighestSubtreeHeight;
}

我真的只是想再次画画。