c++ - 递归函数如何对二叉树进行运算？

Question

我无法理解这个概念。

 void preorderPrint( TreeNode *root ) {

    if ( root != NULL ) {  // (Otherwise, there's nothing to print.)
       cout << root->item << " ";      // Print the root item.
       preorderPrint( root->left );    // Print items in left subtree.
       preorderPrint( root->right );   // Print items in right subtree.
    }
 } 

这如何打印出二叉树中的节点？看起来它只是遍历树，除了根项之外不打印任何内容。

此外，在我看来，使用二叉树的递归函数只是沿直线遍历树。即 root->left 只跟随最左边节点的路径，忽略左子树中的右边节点。这是如何逐步进行的？

Answer 1

您忽略了一个事实，即当一个函数调用另一个函数并且内部函数返回时，另一个函数会从它停止的地方恢复。

考虑一棵具有根节点和左节点的树。发生以下情况:

1. 我们在根节点上调用 preorderPrint。

2. 输出根节点的内容。

3. 它在左节点上调用 preorderPrint。

4. 这将输出左节点的内容。它在 NULL 上调用 preorderPrint 两次，什么也不做，然后返回。

5. 恢复对 preorderPrint 的原始调用，在根节点的右指针(为 NULL)上调用 preorderPrint，并且不执行任何操作。