recursion - 难以理解树遍历递归函数

Question

我在理解前序、中序和后序树遍历中涉及的递归函数时遇到了一些麻烦。我对递归有一些了解（但不可否认，这不是我的强项）。所有这些似乎都调用了自己两次，首先是用根的左孩子打电话，然后是用右孩子打电话。但这到底是怎么可能的呢？用左孩子调用 preOrder 函数不会将控制流返回到顶部，并且永远不会执行下一个调用吗？

void preOrder (Node* root) 
{
    if (root == NULL) return;
    cout<<root->val<<", ";
    preOrder(root->left);
    preOrder(root->right);
}

Answer 1

用左孩子调用 preOrder 函数不会将控制流返回到顶部，并且永远不会执行下一个调用吗？

当然不是。递归调用与任何其他函数调用一样工作：函数完成后，控件返回调用位置。“地点”不仅意味着代码中的点，还意味着调用堆栈上的点，这意味着同一组变量再次可用。就像从任何其他功能返回后一样。

例如，如果你有一棵树

        A
       / \
      X   Y

然后调用节点，然后它首先打印内容，然后调用preorderon并在返回时返回，因此它继续调用on 。AApreorderXpreorder(A)preorderY

Answer 2

void preorder(node *p) {
   if(p) {
     cout << p->val <<"\n";
     preorder(p->left);
     preorder(p->right);
   }
}

Answer 3

Preorder : 处理节点，移到左孩子，移到右孩子

void preorder(Node *root)
{
    if (root == NULL) //<- Check if the currently passed node is empty
        return; //<- if it is, return from the function back down the stack

    cout << root->val << ", "; //<- if it wasn't empty, print its value

    if (root->left != NULL) //<- check if the node to the left is empty
        preorder(root->left); //<- if not recurse to the left child

    if (root->right != NULL) //<- check if the node to the right is empty
        preorder(root->right); //<- if not recurse to the right child
}

中序：向左移动，处理节点，向右移动

void inorder(Node *root)
{
    if (root == NULL)
        return;

    if (root->left != NULL) //<- check if the node to the left is empty
            inorder(root->left); //<- if not recurse to the left child

    cout << root->val << ", ";

    if (root->right != NULL) //<- check if the node to the right is empty
            inorder(root->right); //<- if not recurse to the right child
}

Postorder : 移动到左边节点，移动到右边节点，处理节点

void postorder(Node *root)
{
    if (root == NULL)
        return;

    if (root->left != NULL) //<- check if the node to the left is empty
            postorder(root->left); //<- if not recurse to the left child

    if (root->right != NULL) //<- check if the node to the right is empty
            postorder(root->right); //<- if not recurse to the right child

    cout << root->val << ", "
}