用递归进行二叉树的三种遍历

//功能：分别采用三种方法遍历二叉树，前序，中序，后序三种方法遍历。
//作者：lonkil
//网站: Http://Www.VcFans.Com
//日期: 2008-10-31
//===============================================================
#include "stdafx.h"
#include <malloc.h>
 
//定义一个结构保证数据二叉数的一个节点。
typedef struct  _Bin_Tree
{
	_Bin_Tree *pLeft;//左子树
	_Bin_Tree *pRight;//右子树
	int nData;//节点数据
}Bin_Tree;
 
//将一个节点置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)
{//感谢BaihowFF的提醒，我开始的释放方法是存在问题。
	if ( (*pNode) == 0 ) return;
	ReleaseTree( &((*pNode)->pLeft) );
	ReleaseTree( &((*pNode)->pRight) );
	free( (*pNode) );
	(*pNode) = 0;
}
//前序
void PreOrder(Bin_Tree *pRoot)
{
	if ( pRoot == 0 ) return;
	printf("%d,",pRoot->nData);
	PreOrder(pRoot->pLeft);
	PreOrder(pRoot->pRight);
}
//中序
void InOrder(Bin_Tree *pRoot)
{
	if ( pRoot == 0 ) return;
	InOrder(pRoot->pLeft);
	printf("%d,",pRoot->nData);
	InOrder(pRoot->pRight);
}
//后序
void PostOrder(Bin_Tree *pRoot)
{
	if ( pRoot == 0 ) return;
	PostOrder(pRoot->pLeft);
	PostOrder(pRoot->pRight);
	printf("%d,",pRoot->nData);
}
 
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(pRoot);
	printf("\n");
 
	printf("中序遍历:　");
	InOrder(pRoot);
	printf("\n");
 
	printf("后序遍历:　");
	PostOrder(pRoot);
	printf("\n");
 
	ReleaseTree( &pRoot );
	return 0;
}