二叉树遍历--递归实现

递归这东西真是抽象，我看着看着算法，就囫囵吞枣地的写了下，写得囧了···

这次先用递归实现先序，中序，后序遍历算法。先大概说下原理：我输入一大串字符，中间#就是代表了空，基本的储存结构就是二叉链表。主要就是二叉树的创建和三种顺序的遍历。二叉树的创建通过从左孩子开始创建不断递归，知道读取了#，开始创建对应的右孩子，继续递归。访问的时候对于三种顺序不过就是对于操作的顺序改变而已。

对于下面的程序，按照图里面的二叉树建立方式：输入ABD#G###CE##FH###就建立了按图中的二叉树，然后会输出三种遍历顺序。

（以上图片来源 http://blog.csdn.net/loomman/article/details/4027082 ）

    
      #include <stdio.h>
#include <Windows.h>

#define ElemType char

struct BiTree{
	ElemType num;
	struct BiTree *LeftChild;
	struct BiTree *RightChild;
};
typedef struct BiTree BiTreNode;
typedef BiTreNode* p_BitTree;

VOID PrintElement(ElemType e);
DWORD GetLastErrorBox(HWND hWnd, LPSTR lpTitle) ;
BOOL CreateBinary(p_BitTree* pBiTree);
BOOL PreOrderTraverse(BiTreNode* pBiTree,VOID(*Visit)(ElemType));
BOOL InOrderTraverse(BiTreNode* pBiTree, VOID(*Visit)(ElemType));
BOOL PostOrderTraverse(BiTreNode* pBiTree, VOID(*Visit)(ElemType));


int main()
{

	BiTreNode* T = NULL;
	VOID(*Operate)(ElemType);
	Operate = PrintElement;
	if (!CreateBinary(&T))						//create binary tree
	{
		printf("Create BinaryTree False\n");
		return 0;
	}

	printf("PreOrderTraverse:");				//PreOrderTraverse
	if (!PreOrderTraverse(T,Operate))
	{
		printf("Create BinaryTree False\n");
		return 0;
	}
	printf("\n");

	printf("InOrderTraverse:");					//InOrderTraverse
	if (!InOrderTraverse(T,Operate))
	{
		printf("Create BinaryTree False\n");
		return 0;
	}
	printf("\n");

	printf("PostOrderTraverse:");				//PostOrderTraverse
	if (!PostOrderTraverse(T,Operate))
	{
		printf("Create BinaryTree False\n");
		return 0;
	}
	printf("\n");
	return 0;
}

//创建二叉树
BOOL CreateBinary(p_BitTree* pBiTree)
{
	ElemType ch;
	ch = getchar();
	if (ch == '#')				//输入为#代表空
	{
		(*pBiTree) = NULL;
	}
	else
	{
		(*pBiTree) = (BiTreNode*)calloc(1,sizeof(BiTreNode));		//创建节点
		if (!(*pBiTree))
		{
			printf("Allocate Memory Error\n");
			return FALSE;
		}
		else
		{
			(*pBiTree)->num = ch;									
			CreateBinary(&(*pBiTree)->LeftChild);					//递归调用创建左子树
			CreateBinary(&(*pBiTree)->RightChild);					//递归调用创建右子树
		}
	}
	return TRUE;
}

//先序遍历二叉树
BOOL PreOrderTraverse(BiTreNode* pBiTree, VOID(*Visit)(ElemType))
{
	// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数，
	// 先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
	if (pBiTree) 
	{
		Visit(pBiTree->num);
		PreOrderTraverse(pBiTree->LeftChild, Visit);
		PreOrderTraverse(pBiTree->RightChild, Visit);
		return TRUE;
	} 
	else 
	{
		return FALSE;
	}
} // PreOrderTraverse

//中序遍历二叉树
BOOL InOrderTraverse(BiTreNode* pBiTree, VOID(*Visit)(ElemType))
{
	if (pBiTree) 
	{
		InOrderTraverse(pBiTree->LeftChild, Visit);
		Visit(pBiTree->num);
		InOrderTraverse(pBiTree->RightChild, Visit);
		return TRUE;
	} 
	else 
	{
		return FALSE;
	}
} // InOrderTraverse

//后序遍历二叉树
BOOL PostOrderTraverse(BiTreNode* pBiTree, VOID(*Visit)(ElemType))
{
	if (pBiTree) 
	{
		PostOrderTraverse(pBiTree->LeftChild, Visit);
		PostOrderTraverse(pBiTree->RightChild, Visit);
		Visit(pBiTree->num);
		return TRUE;
	} 
	else 
	{
		return FALSE;
	}
} // InOrderTraverse

//对二叉树元素的操作
VOID PrintElement(ElemType e)
{  // 输出元素e的值
   printf("%c",e);
   return ;
}

// 显示错误信息  
DWORD GetLastErrorBox(HWND hWnd, LPSTR lpTitle)  
{  
	LPVOID lpv;  
	DWORD dwRv;  

	if (GetLastError() == 0) return 0;  

	dwRv = FormatMessage(FORMAT_MESSAGE_ALLOCATE_BUFFER |  
		FORMAT_MESSAGE_FROM_SYSTEM,  
		NULL,  
		GetLastError(),  
		MAKELANGID(LANG_ENGLISH, SUBLANG_ENGLISH_US),  
		(LPSTR)&lpv,  
		0,  
		NULL);  

	MessageBox(hWnd, (LPCSTR)lpv, lpTitle, MB_OK);  

	if(dwRv)  
		LocalFree(lpv);  

	SetLastError(0);  
	return dwRv;  
}  
    
  

二叉树遍历--递归实现