首页 文章

二叉搜索树递归混淆

提问于
浏览 次
1

我认为这是一个愚蠢的问题但很遗憾地说它会清除我的困惑 . 如果您只是查看此代码

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

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

pointers recursion data-structures binary-search-tree traversal

1 回答

  • 1

    当你递归到下一个级别时，这基本上涉及拍摄你的确切位置的快照，然后去做其他事情 . 完成“其他”后，您将返回快照并继续 .

    它与调用非递归函数非常相似 . 当一个函数调用 xyzzy() 时，它会确切地知道从调用返回时继续执行的位置 . 递归函数是相同的，只是它们在向下和向后的路上都经过相同的代码片段 .

    因此，当您返回某个级别（例如，已经处理了左侧的节点）时，您将打印当前节点，然后沿着子树的右侧向下移动 .

    考虑示例树：

    2
 / \
1   4
   / \
  3   5
       \
        6

    要处理此树，请为每个节点（从2开始）处理左节点，打印当前节点值，然后处理右节点 .

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

    “处理”是按顺序打印出给定点（包括该点）下的所有节点 . 这只是一个快乐的效果，如果你从根节点开始，你得到整个树:-)

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

    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.

    如果您检查每条打印行（请参阅 > 标记），您将看到它们按所需顺序出现 .

    回复于

相关问题