无法理解树遍历递归函数-Java 学习之路

我在理解预订，顺序和后序树遍历中涉及的递归函数时遇到了一些麻烦 . 我有一些递归的知识（但不可否认它不是我的强项） . 所有这些人似乎都称自己两次先与根的左子女打电话，然后与正确的孩子打电话 . 但这究竟是怎么可能的呢？对左子项的preOrder函数的调用不会将控制流返回到顶部，并且下一次调用永远不会执行吗？

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

3 回答

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

当然不是 . 递归调用就像任何其他函数调用一样：在函数完成后，控件返回到调用位置 . 'place'不仅意味着代码中的点，还意味着调用堆栈上的点，这意味着同一组变量可以再次使用 . 就像从任何其他功能返回后一样 .

例如，如果你有一棵树
```
A
       / \
      X   Y
```
并且在 A 节点上调用 preorder ，然后它首先打印 A 内容，然后在 X 上调用 preorder ，并在返回时返回到 preorder(A) ，因此它继续在 Y 上调用 preorder .
回复于 2024-04-24T01:50:17+08:00

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
}

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

回复于 2024-04-24T01:50:17+08:00

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

回复于 2024-04-24T01:50:17+08:00

无法理解树遍历递归函数

3 回答

相关问题