由數組建立二叉樹，二叉樹周遊，擷取深度，銷毀

先序周遊：A->B->D->E->C

中序周遊：D->B->E->A->C

後序周遊：D->E->B->C->A

#include <iostream>
typedef char ElemType;
#define EndElem '^'//用^來表示空

typedef struct BiNode
{
	ElemType elem;
	struct BiNode * lchild;
	struct BiNode * rchild;
} * BiTree;

//以先序周遊的方式建立一棵二叉樹
void PreCreateBiTree(BiTree & pnode, ElemType a[], int n)
{
	static int curr = 0;//目前下标
	if (a[curr] == EndElem)
	{
		pnode = NULL;
		curr++;
		if (curr == n)
		{
			curr = 0;//為下一次不同對象調用此函數做好準備
		}
		return;
	}
	pnode = new BiNode;
	pnode->elem = a[curr];
	curr++;
	PreCreateBiTree(pnode->lchild, a, n);
	PreCreateBiTree(pnode->rchild, a, n);
}

//使用二重指針實作，注意調用的時候第一個參數是struct BiNode **;
//void PreCreateBiTree(BiTree * ppnode, ElemType a[], int n)
//{
//	static int curr = 0;/*目前下标*/
//	if (a[curr] == EndElem)
//	{
//		(*ppnode) = NULL;
//		curr++;
//		if (curr == n)
//		{
//			curr = 0;
//		}
//		return;
//	}
//	*ppnode = new BiNode;
//	(*ppnode)->elem = a[curr];
//	curr++;
//	PreCreateBiTree(&((*ppnode)->lchild), a, n);
//	PreCreateBiTree(&((*ppnode)->rchild), a, n);
//}

//先序周遊
void PreTraverseBiTree(BiTree pnode)
{
	if (pnode == NULL)
	{
		return;
	}
	std::cout << pnode->elem << ' ';
	PreTraverseBiTree(pnode->lchild);
	PreTraverseBiTree(pnode->rchild);
}

//中序周遊
void MidTraverseBiTree(BiTree pnode)
{
	if (pnode == NULL)
	{
		return;
	}
	//周遊的不同在于下面三者的順序
	MidTraverseBiTree(pnode->lchild);
	std::cout << pnode->elem << ' ';
	MidTraverseBiTree(pnode->rchild);
}

//後序周遊
void PosTraverseBiTree(BiTree pnode)
{
	if (pnode == NULL)
	{
		return;
	}
	PosTraverseBiTree(pnode->lchild);
	PosTraverseBiTree(pnode->rchild);
	std::cout << pnode->elem << ' ';
}

//擷取深度
int Depth(BiTree pnode)
{
	if (pnode == NULL)
	{
		return 0;
	}
	int leftDepth = Depth(pnode->lchild);
	int rightDepth = Depth(pnode->rchild);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

void DestroyBiTree(BiTree & pnode)
{
	if (pnode == NULL)
	{
		return;
	}
	struct BiNode * pleft = pnode->lchild;
	struct BiNode * pright = pnode->rchild;
	delete pnode;
	DestroyBiTree(pleft);
	DestroyBiTree(pright);
}

int main()
{
	char source[11] = {'A', 'B', 'D', '^',  '^', 'E', '^', '^', 'C', '^', '^'};//按先序周遊排好的數組
	BiTree tree = NULL;
	PreCreateBiTree(tree, source, 11);
	PreTraverseBiTree(tree);	
	std::cout << Depth(tree) << std::endl;
	DestroyBiTree(tree);


	//std::cout << std::endl;
	//BiTree tree2 = NULL;
	//PreCreateBiTree(tree2, source, 11);
	//PosTraverseBiTree(tree2);
	//DestroyBiTree(tree2);

	return 0;
}