二叉搜索树递归混淆

Question

我认为这是一个愚蠢的问题，但很遗憾地说它会消除我的困惑。如果你只看这段代码

void printInOrder(){
        printPrivateInOrder(root);
    }
void printPrivateInOrder(Node* n){
        if (root != NULL){
            if (n->left != NULL){
                printPrivateInOrder(n->left);
            }
            cout << n->val << " ";
            if (n->right != NULL){
                printPrivateInOrder(n->right);
            }
        }
        else{
            cout << "Tree is Empty\n";
        }
    }

在这个Traversal中如果我们走到最左边child，那么这个函数又是怎么调用的呢？假设只看图片 BST Example 我们已经移动到节点4，那么这个函数又是如何被调用的呢？如果 child 都为 null 我不会再次调用此函数，但会再次调用此函数并打印 InOrder Traversal 中的所有节点？怎么样？

Answer 1

当您向下递归到下一个级别时，这基本上涉及拍摄您所在位置的快照，然后再去做其他事情。一旦 "something else" 完成，您 return 到您的快照并继续。

这与调用非递归函数非常相似。当函数调用 xyzzy() 时，它确切地知道在调用 return 时从何处继续。递归函数是相同的，只是它们在向下和向上的过程中都经过 相同的 代码段。

所以，当你回到上一个层级（比如处理完左边的节点），你会打印当前节点，然后往下走右边sub-tree.

的一侧

考虑示例树：

要处理这棵树，对于每个节点（从两个开始），您处理左节点，打印当前节点值，然后处理右节点。

但是，您需要了解 "process the left/right node" 是整个 "process left, print current, process right" 组步骤在其中一个 children 上的重复。从这个意义上说，处理根节点和处理任何其他节点之间没有没有区别。

"processing"是按顺序打印出给定点（包括该点）下的所有节点。如果你从根节点开始，你会得到整棵树，这是一个令人愉快的效果:-)

因此，就实际发生的情况而言，它基本上遵循递归路径：

  2, has a left node 1, process it:
  |  1, has no left node.
> |  1, print 1.
  |  1, has no right node.
  |  1, done.
> 2, print 2.
  2, has a right node 4, process it.
  |  4, has a left node 3, process it.
  |  |  3, has no left node.
> |  |  3, print 3.
  |  |  3, has no right node.
  |  |  3, done.
> |  4, print 4.
  |  4, has a right node 5, process it.
  |  |  5, has no left node.
> |  |  5, print 5.
  |  |  5, has a right node 6, process it.
  |  |  |  6, has no left node.
> |  |  |  6, print 6.
  |  |  |  6, has no right node.
  |  |  |  6, done.
  |  |  5, done.
  |  4, done.
  2, done.

如果您检查每一行打印（请参阅 > 标记），您会发现它们按所需顺序输出。

二叉搜索树递归混淆

Binary Search Tree Recursion Confusion

recursion

pointers

traversal

binary-search-tree

data-structures