难以理解树遍历递归函数

Question

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

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

Answer 1

Preorder：处理节点，向左移动child，向右移动child

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
}

Inorder：向左移动，处理节点，向右移动

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 << ", "
}

Answer 2

用左边的childreturn调用preOrder函数会不会控制流回到顶部，下一个调用永远不会执行？

当然不是。递归调用就像任何其他函数调用一样工作：函数完成后，控件 returns 到调用位置。 'The place' 不仅意味着代码中的点，也意味着调用堆栈上的点，这意味着同一组变量再次可用。就像从任何其他函数 returning 之后一样。

例如，如果你有一棵树

        A
       / \
      X   Y

然后您在 A 节点上调用 preorder，然后它首先打印 A 内容，然后在 X 和 return 它回到了 preorder(A)，因此它继续在 Y 上调用 preorder。

Answer 3

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

难以理解树遍历递归函数

Having trouble understanding tree traversal recursive functions

recursion

binary-tree

binary-search-tree

preorder