二叉树遍历之中序遍历算法（非递归、递归）入门详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了二叉树遍历之中序遍历算法（非递归、递归）入门详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、引言
二叉树的遍历常见的方法有先序遍历、中序遍历、后序遍历和层次遍历等，本文给出了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 );
	} 
}

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;
		} 
	}
}