c++ - 树遍历如何工作？

Question

这是preOrder遍历的代码-

void preOrder(node *root) 
{    
    if(root!=NULL)
    {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }         
}

当我们到达左边的最后一个节点时，它如何到达右边的节点？我的意思是左右节点之间没有链接，尽管它们都有相同的父节点，但在到达最后一个节点后它如何返回到其父节点？

Answer 1

是的!没有 direct同一节点的两个子节点之间的链接。

现在为了帮助您解决上面的递归代码，请看下面这张取自 geeksforgeeks 的图片。

直接跳到最左边的节点 4 ，你知道你是如何到达那里的，现在让我们了解它是如何回到它的父节点等等。

当你从下一行中出来时，你肯定会因为if(root!=NULL)作为4的左 child 和右 child 是空的，还是不明白？别着急，看下面的解释。

现在，您位于最左侧的节点，即 4在这种情况下，负责到达该节点的线路是:

preOrder(root->left)直到现在你还没有看到这条线下面是什么

即您从未见过以下行:

preOrder(root->right); .

4 的左 child 是null ，因此递归条件中断，您最终会看到 preOrder(root->right); .这不是某种魔法，这就是递归。现在当你看到 4 的右 child 时这又是null .

那么，现在 root 的值(value)是多少？

root 的值为 2因为2是将您带到 4 的唯一值首先。递归就像一个级别中的一个级别，当最后一个级别完成时，调用返回到它上面的级别，即 2。对于 4 .最后，下一行将把它带到 2 的 right child这是5 .

preOrder(root->right);

带走:

1)每当你看到cout<<root->data<<" ";您打印当前根的值。

2)每当你看到preOrder(root->left);你移动到 root 的左 child 。

3)每当你看到preOrder(root->right);你移动到 root 的右 child 。

4)如果root的值为NULL你什么都不做，你将被带回调用线路，这将是 preOrder(root->left);或 preOrder(root->right); .

如果我们按照我上面所说的进行操作，您可以猜测给定二叉树的前序遍历将是:

1 2 4 5 3

现在，我建议您阅读并学习递归，然后再解决上述问题。