继续二叉树的三种遍历之非递归法

//功能：分别采用三种方法非递遍历二叉树，前序，中序，后序三种方法遍历。
//作者：lonkil
//网站: Http://Www.VcFans.Com
//日期: 2008-11-2
//===============================================================
#include "stdafx.h"
#include <malloc.h>
 
//定义一个结构保证数据二叉数的一个节点。
typedef struct  _Bin_Tree
{
	_Bin_Tree *pLeft;//左子树
	_Bin_Tree *pRight;//右子树
	int nData;//节点数据
}Bin_Tree;
 
typedef struct _STACK
{
	Bin_Tree *pData;
	_STACK *pNext;
} STACK;
 
//将一个节点置0
void ZeroNode(Bin_Tree *pNode)
{
	pNode->nData = 0;
	pNode->pLeft = 0;
	pNode->pRight = 0;
}
 
//生成一个二叉树
void CreateATree(Bin_Tree *pNode,int n)
{
	Bin_Tree *pLeft=0,*pRight=0;
	if ( pNode == 0 ) return;
 
	pLeft = (_Bin_Tree *)malloc( sizeof(Bin_Tree) );
	ZeroNode( pLeft );
	pLeft->nData = n;
	pRight = (_Bin_Tree *)malloc( sizeof(Bin_Tree) );
	ZeroNode( pRight );
	pRight->nData = n+1;
 
	pNode->pLeft = pLeft;
	pNode->pRight = pRight;	
}
 
//释放一个二叉树所占的内存
void ReleaseTree(Bin_Tree **pNode)
{
	if ( (*pNode) == 0 ) return;
	ReleaseTree( &((*pNode)->pLeft) );
	ReleaseTree( &((*pNode)->pRight) );
	free( (*pNode) );
	(*pNode) = 0;
}
 
//压栈
void push( STACK * pS,STACK **pTop )
{
	if( (*pTop) == 0 )
	{
		(*pTop) = pS;
	}
	else
	{
		pS->pNext = *pTop;
		(*pTop) = pS;//将栈指针上移
	}	
}
 
//出栈
STACK * pop( STACK **pTop )
{
	if ( (*pTop) == 0 ) return 0;
	(*pTop) = (*pTop)->pNext;//栈顶指针下移
	return (*pTop);
}
 
//栈遍历前序
//最要思想:
//第一步将树的左分支的左节点压入栈,最后栈顶将是树最左边节点
//然后从底部将栈中的每个节点放弹出,遍历其右节点,如果右节点还有分支,重复第一步.
void PreOrder_stack( Bin_Tree *pRoot )
{
	STACK *pSTop=0,*pSTemp=0;
	Bin_Tree *pTemp = pRoot;
	if ( pRoot == 0) return;
 
	while ( pTemp || pSTop != 0  )
	{
		if( pTemp )
		{
			STACK *pStack = (STACK *)malloc( sizeof( STACK ) );
			pStack->pData = pTemp;
			pStack->pNext = 0;
			printf("%d,",pTemp->nData);
			push( pStack, &pSTop );
			pTemp = pTemp->pLeft;
		}
		else
		{
			Bin_Tree *pSubRight = pSTop->pData->pRight;
			pSTemp = pSTop;
			pSTop = pop( &pSTop );
			pTemp = pSubRight;
			free(pSTemp);
			pSTemp = 0;
		}
	}
}
 
//栈遍历中序
//主要思想是将按左边寻址的方式，进行寻址，将每个节点压入栈。
//当左子到头后，再出弹栈，这样必然是先左、后中，再右。
void InOrder_stack( Bin_Tree *pRoot )
{
	STACK *pSTop=0,*pSTemp=0;
	Bin_Tree *pTemp = pRoot;
	if ( pRoot == 0) return;
 
	while ( pTemp || pSTop != 0  )
	{
		if( pTemp )
		{
			STACK *pStack = (STACK *)malloc( sizeof( STACK ) );
			pStack->pData = pTemp;
			pStack->pNext = 0;
			push( pStack, &pSTop );
			pTemp = pTemp->pLeft;
		}
		else
		{
			pSTemp = pSTop;
			pSTop = pop( &pSTop );
			printf("%d,",pSTemp->pData->nData);
			pTemp = pSTemp->pData->pRight;
			free(pSTemp);
			pSTemp = 0;
		}
	}
}
 
//栈遍历后序
//主要思想是先遍历左右两个子树，再遍历根节点。
//后序遍历有一个需要主意的地方，就是从右树遍历完后，
//开始弹栈的时候，需要加一个pPre标记，该无数已经访问过,否则无法遍历完成。
void PostOrder_stack( Bin_Tree *pRoot )
{
	STACK *pSTop=0,*pSTemp=0;
	Bin_Tree *pTemp = pRoot, *pPre=0;
	if ( pRoot == 0) return;
 
	while ( pTemp || pSTop != 0  )
	{
		while( pTemp )
		{//遍历左子树
			STACK *pStack = (STACK *)malloc( sizeof( STACK ) );
			pStack->pData = pTemp;
			pStack->pNext = 0;
			push( pStack, &pSTop );
			pTemp = pTemp->pLeft;
		}
		if ( pSTop->pData->pRight == 0 || pPre == pSTop->pData->pRight )
		{//没有右子树或该节点刚被访问过
			printf("%d,", pSTop->pData->nData);
			pSTemp = pSTop;
			pPre = pSTop->pData;
			pSTop = pop( &pSTop );
			pSTemp = 0;	
		}
		else
		{
			pTemp = pSTop->pData->pRight;
		}
	}
}
 
int main(int argc, char* argv[])
{
	Bin_Tree *pRoot=(Bin_Tree *) malloc( sizeof(Bin_Tree) );
	ZeroNode(pRoot);
	pRoot->nData = 0;
	//手工建立深度为3的完全二叉树
	CreateATree( pRoot, 1 );
	CreateATree( pRoot->pLeft,3);
	CreateATree( pRoot->pRight,5);
 
	printf("非递归前序遍历:　");
	PreOrder_stack( pRoot );
	printf("\n");
 
	printf("非递归中序遍历:　");
	InOrder_stack( pRoot );
	printf("\n");
 
	printf("非递归后序遍历:　");
	PostOrder_stack( pRoot );
	printf("\n");
 
	ReleaseTree( &pRoot );
	return 0;
}