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

标签 c++ recursion data-structures tree binary-tree

我无法理解这个概念。

 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 只跟随最左边节点的路径,忽略左子树中的右边节点。这是如何逐步进行的?

最佳答案

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

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

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

  2. 输出根节点的内容。

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

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

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

关于c++ - 递归函数如何对二叉树进行运算?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22600475/

相关文章:

c++ - 我不能在调用 istream 作为参数的函数中使用 ifstream 吗?

c - 为什么函数在代码中没有返回值时返回值给前一个函数?

python - 使用 itertools.accumulate 计算后缀最大值

algorithm - 如何识别一些二叉搜索树遍历是后序还是中序?

c++ - 在 C++ 中读取文件时遇到问题

c++ - 案例 "wrong list": what happens?

c++ - 无法将 QtWebWidgets 添加到项目

node.js - NodeJS 异步和递归

java - 减少属性树

java - toString 导致 StackOverflow 错误