二叉排序树的递归中序遍历

代码很简单，只有几行：
//递归输出二叉树（中序遍历）



       void InTraverse(BiTree &T){

	if(T==NULL)

	    return;

	InTraverse(T->left); //递归遍历左子树

	printf("%d ",T->data.key); //访问根结点

	InTraverse(T->right); //递归遍历右子树

}

但不是很理解，它是怎样递归调用的？函数所创建的（临时）变量是怎样进栈的，然后又怎样返回？二叉树的左右子树是以怎样的顺序进栈的？又是怎样出栈的？能否举个简单的例子说明下？（例如下面的二叉树）
                      4
                 2    5
               1   3

8 个解决方案

#1

我要分哦首先到4，递归到2，因为2不为空，递归到1，因为1不为空到1的左子树，为空就返回到1，把1输出来，然后又递归到1的右子数，为空，返回到1,1这步走完了就返回到2，输出2，又去到2的右子树，3的情况和1相同，输出3，返回到4，输出4，去到4的右子树5，和1相同就输出5，就完了！！

#2

刚开始进入函数的是 4
执行 4 的 left，递归

进入函数的是 2
执行 2 的 left ，递归

进入函数的是 1
执行 1 的 left，递归

进入函数的是NULL
返回执行1的 left 的下一句

输出 1
执行 1 的 right

进入函数的是NULL
返回执行1的 right 的下一句
返回到执行 2 的 left 的下一句

输出 2
执行 2 的 right

进入函数的是 3
............

这样一步步递归，返回，就完成了中序遍历

递归搞懂了就很容易理解，不懂的会看不明白。

#3

我想知道函数创建的变量是如何进栈的？

#4

进栈出栈是由编译器完成的你不用关心

#5

3如果是2的右孩子的话，为1 2 3 4 5
3如果是5的左孩子的话，为1 2 4 3 5

#6

赵老师有经典恢复

#7

1.自己手动模拟执行一遍
2.单步调试，看变量值变化，以及栈信息变化

#8

直接调试，看call stack的变化，自然明白

#1

#2

#3