C语言：资料结构-二叉树的递回遍历演算法
二叉树遍历的概念
（1）遍历二叉树的遍历是指按照一定次序访问树中所有结点，并且每个结点的值仅被访问一次的过程。
（2）遍历的三个子问题及三种访问方式
访问根结点，遍历左子树、遍历右子树先左后右，即先遍历左子树，再遍历右子树，并以根结点访问的次序划分先序、中序、后序先序遍历：先访问根结点，然后遍历左子树，再遍历右子树中序遍历：先遍历左子树，然后访问根结点，最后遍历右子树后序遍历：先遍历左子树，然后遍历右子树，最后访问根结点
先序遍历算法
void Preorder(struct BTreeNode* BT){
if(BT!=NULL) {
printf("%c",BT->data); /*访问根结点*/
Preorder(BT->left); /*先序遍历左子树*/
Preorder(BT->right); /*先序遍历右子树*/
}
}
中序遍历算法
void Inorder(struct BTreeNode* BT){
if(BT!=NULL) {
Inorder(BT->left); /*中序遍历左子树*/
printf("%c",BT->data); /*访问根结点*/
Inorder(BT->right); /*中序遍历右子树*/
}
}
后续遍历算法
void Postorder(struct BTreeNode* BT){
if(BT!=NULL) {
Postorder(BT->left); /*后序遍历左子树*/
Postorder(BT->right); /*后序遍历右子树*/
printf("%c ",BT->data); /*访问根结点*/
}
}
在这三种遍历算法中，访问根结点进行何种操作可视具体应用情况而定，这里暂以打印根结点的值代之。当然若结点的值为使用者定义的记录型别，则还必须依次输出结点值物件中的每个域的值。
递回遍历算法的执行过程
下面以中序递回遍历算法为例，结合图6-9的二叉树，分析其执行过程。
二叉树递回遍历举例
当从其他函式呼叫（此次称为第0次递回呼叫）中序遍历算法时，需要以指向树根A结点的指标Ap作为实参，把它传递给算法中的值参BT，呼叫递回算法时系统自动建立的工作栈应包括BT域和返回地址r域，假定进行第0次递回呼叫后的返回地址为r0，中序遍历左子树后的返回地址（即printf语句的开始地址）为r1，中序遍历右子树后的返回地址（即算法结束的地址）为r2，并假定指向每个结点的指标用该结点的值字尾小写字母p表示，如指向B结点的指标就用Bp表示，则每次进行递回呼叫时工作栈中的资料变化情况如图6-10所示。
二叉树中序递回遍历时工作栈的变化情况
由上述分析中序递回遍历算法的执行过程可知，结点的访问序列为：
C，B，D，A，E，G，F
类似地，若按照先序递回遍历算法和后序递回遍历算法遍历图6-9所示的二叉树，则结点的访问序列分别为：
A，B，C，D，E，F，G和C，D，B，G，F，E，A
