代码之家 › 专栏 › 技术社区 › Fawad Bin Tariq

二叉搜索树递归混淆

traversal binary-search-tree data-structures recursion pointers

Fawad Bin Tariq · 技术社区 · 8 年前

我认为这是一个愚蠢的问题,但很抱歉,这将澄清我的困惑。如果你看看这段代码

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,那么如何再次调用该函数?如果两个子节点都为空,我不会再次调用该函数,但会再次调用该功能并按顺序遍历打印所有节点?怎样

1 回复 | 直到 8 年前

paxdiablo 8 年前

当你递归到下一个级别时,基本上需要拍下你所在位置的快照,然后去做其他事情。一旦“其他东西”完成,您将返回快照并继续。

这和打电话很相似不 -递归函数。当函数调用 xyzzy() ,它确切地知道呼叫返回时从何处继续。递归函数是相同的,除了它们都通过 相同的 一段段代码正在下降和上升。

所以,当你回来的时候 向上的 一个级别(例如,处理了左侧的节点),然后将打印当前节点,然后在子树的右侧向下。

考虑示例树:

要处理此树,对于每个节点(从2开始),处理左节点,打印当前节点值,然后处理右节点。

但是,您需要理解“处理左/右节点”是在其中一个子节点上重复的整个“处理左、打印当前、处理右”步骤集。从这个意义上说不处理根节点和处理任何其他节点之间的差异。

“处理”是按顺序打印出给定点(包括该点)下的所有节点。如果从根节点开始,就会得到整个树,这是一个很好的效果:-)

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

  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.

如果检查每个打印行(请参阅 > 标记),您将看到它们以所需的顺序出现。