二叉树中顺序扫描的实现思想如下。
访问当前节点的左子树；
访问根节点；
访问当前节点的右子树；
图1二叉树
以图1为例，用中序遍历思想遍历该二叉树的过程如下。
访问此二叉树的根节点并找到1；
遍历节点1的左侧子树以找到节点2；
检查节点2左侧的子树以找到节点4。
因为节点4没有左侧子树，所以找到节点4，遍历节点4的右侧子树；
因为节点4没有右边的子树，所以节点2左边的子树遍历完成并访问节点2。
查看节点2的右子树，找到节点5；
因为节点5没有左侧子树，所以访问节点5，而且因为节点5没有右侧子树，所以节点1左侧子树遍历完成，访问节点1，遍历节点1右侧子树以找到节点3；
遍历节点3的左侧子树以找到节点6；
因为节点6没有左侧子树，所以访问节点6，并且因为该节点没有右侧子树，所以节点3左侧子树遍历完成，开始访问节点3，遍历节点3右侧子树以找到节点7；
因为节点7没有左侧子树，所以访问节点7，且因为该节点没有右侧子树，所以节点1右侧子树的遍历完成，即树整体的遍历完成；
因此，使用中顺序扫描获得图1的二叉树的序列如下。
4 2 5 1 6 3 7
递归实现
二叉树中序遍历采用递归思想，可以递归实现，其c语言实现代码如下：
#包含
#包含
#define TElemType int
//创建节点的结构体
typedef struct BiTNode{
t elemtype数据； //数据域
struct BiTNode *lchild，*rchild； //左右孩子的指针
}BiTNode，*BiTree；
//初始化树的函数
voidcreatebitree(bitree*t ) {
*t=(bitnode* ) malloc ) sizeof (bitnode )；
(t ) -数据=1；
(t )-lchild=(bitnode* ) malloc (sizeof ) bitnode )；
(t )-rchild=(bitnode* ) malloc (sizeof ) bitnode )；
(t ) -液晶数据=2；
(t )-lchild-lchild=(bitnode* ) malloc ) sizeof ) bitnode )；
(t )-lchild-rchild=(bitnode* ) malloc ) sizeof ) bitnode )；
(t )-lchild-rchild-data=5；
(t )-LChild-LChild=null；
(t )-LChild-LChild=null；
(t )-Fild-data=3；
(t )-rchild-lchild=(bitnode* ) malloc ) sizeof ) bitnode )；
(t )-rchild-lchild-data=6；
(t )-rchild-lchild-lchild=NULL；
(t )-rchild-lchild-rchild=NULL；
(t )-rchild-rchild=(bitnode* ) malloc ) sizeof ) bitnode )；
(t )-rchild-rchild-data=7；
(t )-rchild-rchild-lchild=NULL；
(t )-rchild-rchild-rchild=NULL；
(t )-lchild-lchild-data=4；
(t )-LChild-LChild=null；
(t )-LChild-LChild=null；
}
//模拟操作节点元素的函数，输出节点自身的数值
语音显示层(bitnode * elem ) {
printf('%d '，elem-data )；
}
//中序遍历
语音识别器(bitreet ) {
if(t ) {
INOrderTraverse(T->lchild);//遍历左孩子
displayElem(T);//调用操作结点数据的函数方法
INOrderTraverse(T->rchild);//遍历右孩子
}
//如果结点为空，返回上一层
return;
}
int main() {
BiTree Tree;
CreateBiTree(&Tree);
printf("中序遍历算法: n");
INOrderTraverse(Tree);
}
运行结果：
中序遍历算法:
4 2 5 1 6 3 7
非递归实现
而递归的底层实现依靠的是栈存储结构，因此，二叉树的先序遍历既可以直接采用递归思想实现，也可以使用栈的存储结构模拟递归的思想实现。
中序遍历的非递归方式实现思想是：从根结点开始，遍历左孩子同时压栈，当遍历结束，说明当前遍历的结点没有左孩子，从栈中取出来调用操作函数，然后访问该结点的右孩子，继续以上重复性的操作。
除此之外，还有另一种实现思想：中序遍历过程中，只需将每个结点的左子树压栈即可，右子树不需要压栈。当结点的左子树遍历完成后，只需要以栈顶结点的右孩子为根结点，继续循环遍历即可。
两种非递归方法实现二叉树中序遍历的代码实现为：
#include
#include
#define TElemType int
int top=-1;//top变量时刻表示栈顶元素所在位置
//构造结点的结构体
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
*T=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->data=1;
(*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->data=2;
(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=5;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;
(*T)->rchild->data=3;
(*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=6;
(*T)->rchild->lchild->lchild=NULL;
(*T)->rchild->lchild->rchild=NULL;
(*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->rchild->data=7;
(*T)->rchild->rchild->lchild=NULL;
(*T)->rchild->rchild->rchild=NULL;
(*T)->lchild->lchild->data=4;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;
}
//前序和中序遍历使用的进栈函数
void push(BiTNode** a,BiTNode* elem){
a[++top]=elem;
}
//弹栈函数
void pop( ){
if (top==-1) {
return ;
}
top--;
}
//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){
printf("%d ",elem->data);
}
//拿到栈顶元素
BiTNode* getTop(BiTNode**a){
return a[top];
}
//中序遍历非递归算法
void InOrderTraverse1(BiTree Tree){
BiTNode* a[20];//定义一个顺序栈
BiTNode * p;//临时指针
push(a, Tree);//根结点进栈
while (top!=-1) {//top!=-1说明栈内不为空，程序继续运行
while ((p=getTop(a)) &&p){//取栈顶元素，且不能为NULL
push(a, p->lchild);//将该结点的左孩子进栈，如果没有左孩子，NULL进栈
}
pop();//跳出循环，栈顶元素肯定为NULL，将NULL弹栈
if (top!=-1) {
p=getTop(a);//取栈顶元素
pop();//栈顶元素弹栈
displayElem(p);
push(a, p->rchild);//将p指向的结点的右孩子进栈
}
}
}
//中序遍历实现的另一种方法
void InOrderTraverse2(BiTree Tree){
BiTNode* a[20];//定义一个顺序栈
BiTNode * p;//临时指针
p=Tree;
//当p为NULL或者栈为空时，表明树遍历完成
while (p || top!=-1) {
//如果p不为NULL，将其压栈并遍历其左子树
if (p) {
push(a, p);
p=p->lchild;
}
//如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树
else{
p=getTop(a);
pop();
displayElem(p);
p=p->rchild;
}
}
}
int main(){
BiTree Tree;
CreateBiTree(&Tree);
printf("中序遍历算法1: n");
InOrderTraverse1(Tree);
printf("n中序遍历算法2: n");
InOrderTraverse2(Tree);
}
运行结果
中序遍历算法1:
4 2 5 1 6 3 7
中序遍历算法2:
4 2 5 1 6 3 7