非递归遍历二叉树的四种策略-先序、中序、后序和层序

遍历二叉树的递归算法，是比较容易理解的，但是非递归的循环算法不是很容易一眼看穿。下面的五个算法是参考严蔚敏的《数据结构》和USTC的张昱老师的讲义后，写下来的，部分有改动。

先序遍历二叉树算法1

// Copyright (c) 2009, ALex ZhonG. All rights reserved.

Status PreOrderTraverse(BiTree T, Status (Visit *)(TElemType e))
{
	InitStack(S);
	Push(S, T);
	p = T;//或 GetTop(S, p);
	while(!StackEmpty(S) && p)
	{
		while(p)
		{
			if(!Visit(p->data))
				return ERROR;
			Push(p->rchild); 
			p = p->lchild;
		}
		Pop(S, p);
	}
	DestroyStack(S);
	return OK;
}

先序遍历二叉树算法2

// Copyright (c) 2009, ALex ZhonG. All rights reserved.

Status PreOrderTraverse(BiTree T, Status (Visit *)(TelemType))
{
	InitStack(S);
	Push(S, T);
	p = T;
	while(!StackEmpty(S) && p)
	{
		while(p)
		{
			if(!Visit(p->data))
				return ERROR;
			Push(S, p);
			p = p->lchild;
		}
		if(!StackEmpty(S))
		{
			Pop(S, p);
			p = p->rchild;
		}
	}
	DestroyStack(S);
	return OK;
}

中序遍历二叉树算法

// Copyright (c) 2009, ALex ZhonG. All rights reserved.

Status InOrderTraverse(BiTree T, Status (Visit *)(TelemType e))
{
	InitStack(S);
	Push(S, T)'
	p = T;
	while(!StackEmpty(S) && p)
	{
		while(p)
		{
			Push(S, p);
			p = p ->lchild;
		}
		Pop(S, p);
		if(!Visit(p->data))
			return ERROR;
		p = p->rchild;
	}
	DestroyStack(S);
	return OK;
}

后序遍历二叉树算法

// Copyright (c) 2009, ALex ZhonG. All rights reserved.

Status PostOrderTraverse(BiTree T, Status (Visit *)(TelemType e))
{
	InitStack(S);
	Push(S, T);
	p = T;
	while(!StackEmpty(S) && p)
	{
		if(p)
		{／／一直走到最左下的结点
			Push(S, p);
			p = p->lchild;
		}
		else
		{//p为NULL时
			GetTop(S, p);
			if(p->rchild && p->rchild != r)
			{//p有右孩子或p的右孩子不是刚刚被访问的
				p = p->rchild;
				Push(S, p);
				p = p->lchild;
			}
			else
			{//p无右孩子或p右孩子刚刚被访问过时
				Pop(S, p);
				Visit(p->data);
				r = p;
				p = NULL;
			}
		}
	}
	DestroyStack(S);
	return OK;
}

层序遍历二叉树算法

// Copyright (c) 2009, ALex ZhonG. All rights reserved.

Status LevelOrderTraverse(BiTree T, Status (Visit *)(TelemType e))
{
	InitQueue(Q);
	p = T;
	if(p)
	{
		if(!Visit(p->data)
			return ERROR;
		EnQueue(Q, p->lchild);
		EnQueue(Q, p->rchild);
		while(Q)
		{
			DeQueue(Q, p);
			if(!Visit(p->data))
				return ERROR;
			if(p->lchild)
				EnQueue(Q, p->lchild);
			if(p->rchild)
				EnQueue(Q, p->rchild);
		}
	}
	return OK;
}

欢迎讨论、批评和指正！

ALex ZhonG