关于二分搜索树的遍历问题
来源：5-5 二分搜索树的遍历（深度优先遍历）
Squirre_lMan
2017-03-25
void preOrder(Node* node){
if( node != NULL ){
cout<<node->key<<endl;
preOrder(node->left);
preOrder(node->right);
}
}
请教老师和同学：比如这个前序遍历，按照根左右的方式，先打印根节点，之后递归，一直打印它的左节点。递归到了最后一个子树的时候，打印完了它的左节点，此时又递归了一次，但是这个时候已经没有左节点了，节点为空，那么右节点的递归是怎么执行的？
2回答
-
这里的关键是，递归是会返回的！
当在叶子节点的时候，此时，先判断这个叶子节点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)。
如果这个过程不理解，可以考虑做一棵不要太深的树，比如三层，然后在前序遍历的时候，一步一步的跟踪看看，代码是怎样执行的：）
422017-03-26 -
北京小程序员
2017-03-25
最简单的递归问题，当递归到最后左子树preOrder（NULL），所以这个递归不执行，然后就去执行preOrder（right）了啊
012017-03-26
相似问题