无法理解树遍历递归函数 [英] Having trouble understanding tree traversal recursive functions

问题描述

我在理解涉及预序，有序和后序树遍历的递归函数时遇到了一些麻烦.我对递归有所了解(但是请记住，这不是我的强项).似乎所有的人都给自己打电话两次，首先与根的左孩子打个电话，然后与右孩子打个电话.但是这怎么可能呢?带有左子元素的对preOrder函数的调用会不会使控制流回到顶部，而下一个调用将永远不会执行?

I am having some trouble understanding the recursive functions involved in preorder, inorder, and postorder tree traversal. I have some knowledge of recursion (but admittedly its not my strong suit). All of the seem to call themselves twice first making a call with the left child of the root and then with the right child. But how exactly is this possible? Wouldn't the call to the preOrder function with the left child return the flow of control back to the top, and the next call would never be executed?

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

推荐答案

使用左子元素调用preOrder函数不会将控制流返回到顶部，因此下一个调用永远不会被执行?

当然不是.递归调用的工作方式与其他任何函数调用一样:函数完成后，控件将返回到调用位置. 位置"不仅意味着代码中的点，还意味着调用堆栈上的点，这意味着同一组变量可以再次使用.就像从其他任何函数返回后一样.

Of course not. The recursive call works just like any other function call: after the function completion the control returns to the place of call. 'The place' means not only the point in the code but also the point on the call stack, which means the same set of variables is available again. Just like after returning from any other function.

例如，如果您有一棵树

        A
       / \
      X   Y

，然后在A节点上调用preorder，然后它首先打印A内容，然后在X上调用preorder，并在返回时返回preorder(A)，因此继续进行操作调用Y上的preorder.

and you call preorder on the A node, then it first prints the A contents, then calls preorder on X and on return it is back in preorder(A), so it proceeds to call preorder on Y.

这篇关于无法理解树遍历递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！