第一：寫自己的頭文件”BTree.h“

#ifndef _B_TREE_H_#define _B_TREE_H_#define LEFT_CHILD		1   //左孩子#define RIGHT_CHILD		2   //右孩子typedef struct BTREE{	NODE_TYPE value;	struct BTREE *leftChild;	struct BTREE *rightChild;}BTREE;#endif
第二: 通過字符串 a(b,c)輸入二叉樹
首先我們將錄入的字符串分為以下六種狀態(tài)：//定義字符串的六種狀態(tài)#define BTREE_STATUS_BEGIN 1 //開始#define BTREE_STATUS_END 2 //結(jié)束#define BTREE_STATUS_ALPHA 3//字符#define BTREE_STATUS_LEFT_BRACKET 4//左括號#define BTREE_STATUS_RIGHT_BRACKET 5//右括號#define BTREE_STATUS_COMMA 6//逗號剛開始為開始狀態(tài)，然后根據(jù)狀態(tài)進(jìn)行轉(zhuǎn)換。
#include<stdio.h>#include<malloc.h>#include<string.h>#include"MecTool.h"typedef char NODE_TYPE;#include"BTree.h"typedef BTREE *USER_TYPE;#include"MecStack.h"//定義字符串的六種狀態(tài)#define BTREE_STATUS_BEGIN				1 //開始#define BTREE_STATUS_END				2 //結(jié)束#define BTREE_STATUS_ALPHA				3	//字符#define BTREE_STATUS_LEFT_BRACKET		4	//左括號#define BTREE_STATUS_RIGHT_BRACKET		5	//右括號#define BTREE_STATUS_COMMA				6	//逗號//將需要用到的變量封裝起來typedef struct{	int status;   //狀態(tài)	boolean Ok; //是否正確	boolean finished; //是否	int index; //處理的字符位置	int whichChild; //處理的哪一個孩子;	BTREE *root; //指向的二叉樹	BTREE *node;  //指向新生成的節(jié)點(diǎn)	MEC_STACK *nodePointStack; //指向棧}BTREE_PARA;boolean PRocessBtreeComma(char ch, BTREE_PARA *para){	if(isalpha(ch)){		dealAlpha(ch, para);		para->index++;		para->status = BTREE_STATUS_ALPHA;	}else if(')' == ch){		dealRightBracket(para);		para->index++;		para->status = BTREE_STATUS_RIGHT_BRACKET;	}else{		para->Ok = FALSE;	}	return para->Ok;}boolean processBtreeRightBracket(char ch, BTREE_PARA *para){	if(',' == ch){		dealComma(para);		para->index++;		para->status = BTREE_STATUS_COMMA;	}else if(')' == ch){		if(FALSE == dealRightBracket(para)){			return para->Ok;		}		para->index++;		para->status = BTREE_STATUS_RIGHT_BRACKET;		printf("zheli:%d/n",para->Ok);	}else if(0 == ch){		para->status = BTREE_STATUS_END;	}else		printf("輸出錯誤!/n");	return para->Ok;}boolean processBtreeLeftBracket(char ch, BTREE_PARA *para){	if(isalpha(ch)){		dealAlpha(ch, para);		para->index++;		para->status = BTREE_STATUS_ALPHA;	}else if(',' == ch){		dealComma(para);		para->index++;		para->status = BTREE_STATUS_COMMA;	}else 		printf("輸出錯誤!/n");	return para->Ok;}/*	字符狀態(tài)表示我已經(jīng)處理完了這個字符,看看需要變成什么狀態(tài)*/boolean processBtreeAlpha(char ch, BTREE_PARA *para){	if('(' == ch){		if(FALSE ==dealLeftBracket(para)){			return para->Ok;		}		para->index++;		para->status = BTREE_STATUS_LEFT_BRACKET;	}else if(')' == ch){		dealRightBracket(para);		para->index++;		para->status = BTREE_STATUS_RIGHT_BRACKET;	}else if(',' == ch){		dealComma(para);		para->index++;		para->status = BTREE_STATUS_COMMA;	}else if(0 == ch){		para->status = BTREE_STATUS_END;	}else{		printf("輸出錯誤!/n");		para->Ok = FALSE;	}	return para->Ok;}boolean processBtreeEnd(BTREE **pMainRoot, BTREE_PARA *para){	*pMainRoot = para->root;//就是bt指向的空間 == para->root	para->finished = TRUE;	return para->Ok;}boolean processBtreeBegin(char ch, BTREE_PARA *para){	//判斷是不是一個字母	if(isalpha(ch)){		dealAlpha(ch, para);		para->index++;//指向下一個字符		para->status = BTREE_STATUS_ALPHA;//變成字符狀態(tài)	}else{		printf("輸入的字符有問題");		return FALSE;	}	return para->Ok;}boolean createBtreeByString(char *str, BTREE **bt){		BTREE_PARA para ={		 BTREE_STATUS_BEGIN,		 TRUE,		 FALSE,		 0,		 LEFT_CHILD,		 *bt,		NULL,		NULL,	};	if(para.root != NULL){		printf("二叉樹存在");		return FALSE;	}	//初始化棧,需要兩個參數(shù),一個是指向棧的指針的地址值,還有申請空間。	initMecStack(?.nodePointStack, strlen(str) / 2);	//分狀態(tài)處理字符串	while(para.Ok && !para.finished){		para.index = skipBlank(str, para.index); //跳過空白		if(BTREE_STATUS_BEGIN == para.status){			processBtreeBegin(str[para.index], ?);		}else if(BTREE_STATUS_END == para.status){			processBtreeEnd(bt, ?);		}else if(BTREE_STATUS_ALPHA == para.status){			processBtreeAlpha(str[para.index], ?);		}else if(BTREE_STATUS_LEFT_BRACKET == para.status){			processBtreeLeftBracket(str[para.index], ?);		}else if(BTREE_STATUS_RIGHT_BRACKET == para.status){			processBtreeRightBracket(str[para.index], ?);		}else if(BTREE_STATUS_COMMA == para.status){			processBtreeComma(str[para.index], ?);		}	}	return para.Ok;}void main(){	char str[80] = {0};	BTREE *btree = NULL;	BTREE *btreeCopy = NULL;	int depth = 0;	int count = 0;	printf("請輸入一個二叉樹A(B,C):");	gets(str);	if(TRUE == createBtreeByString(str, &btree))		printf("表達(dá)式正常!/n");	printf("先序遍歷是");	showFirstTree(btree);	printf("/n");	printf("中序遍歷是");	showMiddleTree(btree);	printf("/n");	printf("后序遍歷是");	showAfterTree(btree);	printf("/n");	depth = getTreeDepth(btree);	printf("樹的深度是:%d", depth);	printf("/n");	getTreeCount(btree, &count);	printf("樹的葉子節(jié)點(diǎn)個數(shù)是:%d", count);	printf("/n");	btreeCopy = copyTree(btree);	printf("先序遍歷是");	showFirstTree(btreeCopy);}處理字符：將字符存儲起來,通過讀取棧頂元素將其鏈接它的雙親節(jié)點(diǎn)上。
boolean dealAlpha(char ch, BTREE_PARA *para){	BTREE *parent = NULL;//存放棧頂元素		para->node = (BTREE *)calloc(sizeof(BTREE), 1);	para->node->value = ch;	if(NULL == para->root)//是第一個節(jié)點(diǎn)	{		para->root = para->node;	}else{		if(readTop(*para->nodePointStack, &parent) == FALSE){			printf("讀取棧頂元素失敗");			para->Ok = FALSE;			return para->Ok;		}		if(LEFT_CHILD == para->whichChild){			parent->leftChild = para->node;		}else{			parent->rightChild = para->node;		}	}	return para->Ok;}處理右括號，只需要將根節(jié)點(diǎn)出棧即可(棧中存儲的都是有孩子且沒有輸入的節(jié)點(diǎn))
boolean dealRightBracket(BTREE_PARA *para){	BTREE* value;	pop(para->nodePointStack, &value);//根節(jié)點(diǎn)出棧	return para->Ok;}處理左括號,碰見左括號證明左括號前面的字符是一個雙親節(jié)點(diǎn)且子節(jié)點(diǎn)沒有錄入，要把這個字符入棧。
boolean dealLeftBracket(BTREE_PARA *para){	//根節(jié)點(diǎn)入棧	push(para->nodePointStack,para->node);	//下一個字母是左子樹	para->whichChild = LEFT_CHILD;	return para->Ok;}處理逗號，都要證明下一個字符是右孩子
boolean dealComma(BTREE_PARA *para){	//下一個將要連接右孩子	para->whichChild = RIGHT_CHILD;	return para->Ok;}上面的函數(shù)可以實現(xiàn)從鍵盤輸入類似于A（B，C）的字符創(chuàng)建二叉樹的功能
二叉樹的常見遍歷操作
1 遍歷操作：
每個節(jié)點(diǎn)都會被左三次，此時不同的就是輸出時刻。
先序遍歷：根節(jié)點(diǎn)先輸出
void showFirstTree(BTREE *root){	if(root == NULL)		return;	printf("%c /t", root->value);	showFirstTree(root->leftChild);	showFirstTree(root->rightChild);
中序遍歷：根節(jié)點(diǎn)先輸出
void showMiddleTree(BTREE *root){	if(root == NULL)		return;	showMiddleTree(root->leftChild);	printf("%c /t", root->value);	showMiddleTree(root->rightChild);}后序遍歷：根節(jié)點(diǎn)最后輸出
void showAfterTree(BTREE *root){	if(root == NULL)		return;	showAfterTree(root->leftChild);	showAfterTree(root->rightChild);	printf("%c /t", root->value);}}
2 求二叉樹的深度
二叉樹的深度 等于左子樹和右子樹其中較大的一個加上1使用遞歸
int getTreeDepth(BTREE *root){	int depth = 0;	int depthLeft = 0;	int depthRight = 0;	if(root == NULL){		return depth;//葉子節(jié)點(diǎn),它的高度是0	}else{		depthLeft = getTreeDepth(root->leftChild);//得到非葉子節(jié)點(diǎn)左子樹高度		depthRight = getTreeDepth(root->rightChild);//得到非葉子節(jié)點(diǎn)右子樹高度		depth = ((depthLeft > depthRight)? depthLeft :depthRight) + 1;	}	return depth;}
3 復(fù)制一個二叉樹
BTREE* copyTree(BTREE *root){	BTREE *p = NULL;//指向這個將要生成的節(jié)點(diǎn)	BTREE *leftLink = NULL;//指向?qū)⒁晒?jié)點(diǎn)的左孩子	BTREE *rightLink = NULL;//右孩子	if(root == NULL)		return;	if(root->leftChild != NULL)//這個要復(fù)制的節(jié)點(diǎn)的左孩子不是空	{		leftLink = copyTree(root->leftChild);//復(fù)制這個左孩子	}else		leftLink = NULL;	if(root->rightChild != NULL)//這個要復(fù)制的節(jié)點(diǎn)的左孩子不是空	{		rightLink = copyTree(root->rightChild);//復(fù)制這個左孩子	}else		rightLink = NULL;	//為新生成的節(jié)點(diǎn)申請空間	if((p = (BTREE *)calloc(sizeof(BTREE), 1)) == NULL){		printf("申請空間失敗");	}	p->leftChild = leftLink;	p->rightChild = rightLink;	p->value = root->value;	return p;}
3 求葉子節(jié)點(diǎn)數(shù)
void getTreeCount(BTREE *root, int *pcount){	if(root == NULL){		return;	}	if(root->leftChild == NULL && root->rightChild == NULL){		(*pcount)++;	}//葉子節(jié)點(diǎn)的左孩子和右孩子都是空	getTreeCount(root->leftChild, pcount);	getTreeCount(root->rightChild, pcount);}