二叉树遍历之中序遍历算法（非递归、递归）入门详解_二叉树中序遍历

一、引言
二叉树的遍历常见的方法有先序遍历、中序遍历、后序遍历和层次遍历等，本文给出了C语言版本的中序遍历二叉树的非递归算法和递归算法。
中序遍历的原理很简单，也就是把树根的访问放在中间。访问结点的次序是：“左—>根—>右”，也就是首先访问左子树，之后访问树根，最后访问右子树。对于左、右子树而言，其访问的次序依然是“左—>根—>右”。
不要小看这里的次序发生的改变，其实具体的实现方式比先序遍历也要麻烦了。
二叉树的中序遍历与先序遍历一样，都可以通过递归算法实现，也可以通过非递归算法实现。
二、二叉树的中序遍历详细演示过程
1、假设二叉树（左右子树全）如下图所示：

2、假设二叉树（没有右子树）如下图所示：

3、假设二叉树（没有左子树）如下图所示：

4、对于稍微复杂一点的二叉树，如下图所示：

其中序遍历过程演示如下（“左—>根—>右”）

三、先序遍历二叉树的代码：
1、算法具体实现思路
从树根开始依次向左走，见到一个结点就入栈一个，直到踏空，然后栈顶结点弹栈，弹栈结点立即访问，之后沿着该结点向右走一步，然后重复前面的动作一路向左。
2、递归算法

void  InorderSearch( BiTree *T )
{
	if( T != NULL )
	{
		InorderSearch( T->Lchild );
#ifdef CHAR
		printf( "%5c\n", T->data );
#else
		printf( "%5d\n", T->data );
#endif  
		InorderSearch( T->Rchild );
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2、非递归算法

void InorderSearch( BiTree *T )
{
	BiTree *stack[MAX_NODE], *p = T;
	int top = 0;
	if (T==NULL) 
	{
		printf( "二叉树为空." );
		return;
	}
	while( p != NULL || top > 0 )
	{
		if( p != NULL )//遇到非空结点即压栈，之后一路向左 
		{
			stack[top++] = p; 
			p = p->Lchild;
		}
		else//遇到空节点则弹栈，访问，向右一步走 
		{
			p = stack[--top]; 
#ifdef CHAR
			printf( "%5c\n", p->data );
#else
			printf( "%5d\n", p->data );
#endif 
			p = p->Rchild;
		} 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

补充：至此，已经完成了二叉树的创建的三种不同方法、二叉树遍历的两种方法。对于中序遍历，其实还有很多方法，但是笔者比较喜欢上述方法，两个字“简单”。