遞歸這東西真是抽象，我看著看著算法，就囫圇吞棗地的寫(xiě)了下，寫(xiě)得囧了···

這次先用遞歸實(shí)現(xiàn)先序，中序，后序遍歷算法。先大概說(shuō)下原理：我輸入一大串字符，中間#就是代表了空，基本的儲(chǔ)存結(jié)構(gòu)就是二叉鏈表。主要就是二叉樹(shù)的創(chuàng)建和三種順序的遍歷。二叉樹(shù)的創(chuàng)建通過(guò)從左孩子開(kāi)始創(chuàng)建不斷遞歸，知道讀取了#，開(kāi)始創(chuàng)建對(duì)應(yīng)的右孩子，繼續(xù)遞歸。訪問(wèn)的時(shí)候?qū)τ谌N順序不過(guò)就是對(duì)于操作的順序改變而已。

對(duì)于下面的程序，按照?qǐng)D里面的二叉樹(shù)建立方式：輸入ABD#G###CE##FH###就建立了按圖中的二叉樹(shù)，然后會(huì)輸出三種遍歷順序。

（以上圖片來(lái)源 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;
}

//創(chuàng)建二叉樹(shù)
BOOL CreateBinary(p_BitTree* pBiTree)
{
	ElemType ch;
	ch = getchar();
	if (ch == '#')				//輸入為#代表空
	{
		(*pBiTree) = NULL;
	}
	else
	{
		(*pBiTree) = (BiTreNode*)calloc(1,sizeof(BiTreNode));		//創(chuàng)建節(jié)點(diǎn)
		if (!(*pBiTree))
		{
			printf("Allocate Memory Error\n");
			return FALSE;
		}
		else
		{
			(*pBiTree)->num = ch;									
			CreateBinary(&(*pBiTree)->LeftChild);					//遞歸調(diào)用創(chuàng)建左子樹(shù)
			CreateBinary(&(*pBiTree)->RightChild);					//遞歸調(diào)用創(chuàng)建右子樹(shù)
		}
	}
	return TRUE;
}

//先序遍歷二叉樹(shù)
BOOL PreOrderTraverse(BiTreNode* pBiTree, VOID(*Visit)(ElemType))
{
	// 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)，
	// 先序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。
	if (pBiTree) 
	{
		Visit(pBiTree->num);
		PreOrderTraverse(pBiTree->LeftChild, Visit);
		PreOrderTraverse(pBiTree->RightChild, Visit);
		return TRUE;
	} 
	else 
	{
		return FALSE;
	}
} // PreOrderTraverse

//中序遍歷二叉樹(shù)
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

//后序遍歷二叉樹(shù)
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

//對(duì)二叉樹(shù)元素的操作
VOID PrintElement(ElemType e)
{  // 輸出元素e的值
   printf("%c",e);
   return ;
}

// 顯示錯(cuò)誤信息  
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;  
}  
    
  

二叉樹(shù)遍歷--遞歸實(shí)現(xiàn)