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

這次先用遞歸實現先序，中序，后序遍歷算法。先大概說下原理：我輸入一大串字符，中間#就是代表了空，基本的儲存結構就是二叉鏈表。主要就是二叉樹的創建和三種順序的遍歷。二叉樹的創建通過從左孩子開始創建不斷遞歸，知道讀取了#，開始創建對應的右孩子，繼續遞歸。訪問的時候對于三種順序不過就是對于操作的順序改變而已。

對于下面的程序，按照圖里面的二叉樹建立方式：輸入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;  
}  
    
  

二叉樹遍歷--遞歸實現