关于二分搜索树的遍历问题

Question

 void preOrder(Node* node){

        if( node != NULL ){
            cout<<node->key<<endl;
            preOrder(node->left);
            preOrder(node->right);
        }
    }

请教老师和同学：比如这个前序遍历，按照根左右的方式，先打印根节点，之后递归，一直打印它的左节点。递归到了最后一个子树的时候，打印完了它的左节点，此时又递归了一次，但是这个时候已经没有左节点了，节点为空，那么右节点的递归是怎么执行的？

Answer 1

liuyubobobo 2017-03-26 00:02:57

这里的关键是，递归是会返回的！

当在叶子节点的时候，此时，先判断这个叶子节点if(node!=NULL)，进入了if语句，之后cout打印了这个叶子节点的信息。之后在这个叶子节点调用了preOrder(node->left)，去尝试递归打印这个叶子节点的左节点。这个叶子的左节点为空，所以其实我们调用了一次preOrder(NULL)。这次preOrder在if(node!=NULL)的时候判断失败，preOrder直接完成，这次preOrder结束，会回到了叶子节点执行完preOrder(node->left)的地方，将继续执行下一句preOrder(node->right)，去尝试递归打印这个叶子节点的右节点。这个叶子的右节点也为空，返回以后，又回到了叶子节点，此时叶子节点的所有语句也已经完成，继续返回，返回到上一层节点之前调用preOrder(node->left)的地方，继续执行preOrder(node->right)。

如果这个过程不理解，可以考虑做一棵不要太深的树，比如三层，然后在前序遍历的时候，一步一步的跟踪看看，代码是怎样执行的：）

• 提问者 Squirre_lMan #1

  谢谢老师，关键在于递归为空时会返回上一次递归执行时的语句，已经明白了！

• liuyubobobo 回复 提问者 Squirre_lMan #2

  赞！加油！：）

Answer 2

北京小程序员 2017-03-25 20:52:16

最简单的递归问题，当递归到最后左子树preOrder（NULL），所以这个递归不执行，然后就去执行preOrder（right）了啊

• 提问者 Squirre_lMan #1

  谢谢，是我对递归理解的还不是很好，现在明白了。