第一：寫自己的頭文件”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)輸入二叉樹
首先我們將錄入的字符串分為以下六種狀態：//定義字符串的六種狀態#define BTREE_STATUS_BEGIN 1 //開始#define BTREE_STATUS_END 2 //結束#define BTREE_STATUS_ALPHA 3//字符#define BTREE_STATUS_LEFT_BRACKET 4//左括號#define BTREE_STATUS_RIGHT_BRACKET 5//右括號#define BTREE_STATUS_COMMA 6//逗號剛開始為開始狀態，然后根據狀態進行轉換。
#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"//定義字符串的六種狀態#define BTREE_STATUS_BEGIN				1 //開始#define BTREE_STATUS_END				2 //結束#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;   //狀態	boolean Ok; //是否正確	boolean finished; //是否	int index; //處理的字符位置	int whichChild; //處理的哪一個孩子;	BTREE *root; //指向的二叉樹	BTREE *node;  //指向新生成的節點	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;}/*	字符狀態表示我已經處理完了這個字符,看看需要變成什么狀態*/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;//變成字符狀態	}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;	}	//初始化棧,需要兩個參數,一個是指向棧的指針的地址值,還有申請空間。	initMecStack(?.nodePointStack, strlen(str) / 2);	//分狀態處理字符串	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("表達式正常!/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("樹的葉子節點個數是:%d", count);	printf("/n");	btreeCopy = copyTree(btree);	printf("先序遍歷是");	showFirstTree(btreeCopy);}處理字符：將字符存儲起來,通過讀取棧頂元素將其鏈接它的雙親節點上。
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)//是第一個節點	{		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;}處理右括號，只需要將根節點出棧即可(棧中存儲的都是有孩子且沒有輸入的節點)
boolean dealRightBracket(BTREE_PARA *para){	BTREE* value;	pop(para->nodePointStack, &value);//根節點出棧	return para->Ok;}處理左括號,碰見左括號證明左括號前面的字符是一個雙親節點且子節點沒有錄入，要把這個字符入棧。
boolean dealLeftBracket(BTREE_PARA *para){	//根節點入棧	push(para->nodePointStack,para->node);	//下一個字母是左子樹	para->whichChild = LEFT_CHILD;	return para->Ok;}處理逗號，都要證明下一個字符是右孩子
boolean dealComma(BTREE_PARA *para){	//下一個將要連接右孩子	para->whichChild = RIGHT_CHILD;	return para->Ok;}上面的函數可以實現從鍵盤輸入類似于A（B，C）的字符創建二叉樹的功能
二叉樹的常見遍歷操作
1 遍歷操作：
每個節點都會被左三次，此時不同的就是輸出時刻。
先序遍歷：根節點先輸出
void showFirstTree(BTREE *root){	if(root == NULL)		return;	printf("%c /t", root->value);	showFirstTree(root->leftChild);	showFirstTree(root->rightChild);
中序遍歷：根節點先輸出
void showMiddleTree(BTREE *root){	if(root == NULL)		return;	showMiddleTree(root->leftChild);	printf("%c /t", root->value);	showMiddleTree(root->rightChild);}后序遍歷：根節點最后輸出
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;//葉子節點,它的高度是0	}else{		depthLeft = getTreeDepth(root->leftChild);//得到非葉子節點左子樹高度		depthRight = getTreeDepth(root->rightChild);//得到非葉子節點右子樹高度		depth = ((depthLeft > depthRight)? depthLeft :depthRight) + 1;	}	return depth;}
3 復制一個二叉樹
BTREE* copyTree(BTREE *root){	BTREE *p = NULL;//指向這個將要生成的節點	BTREE *leftLink = NULL;//指向將要生成節點的左孩子	BTREE *rightLink = NULL;//右孩子	if(root == NULL)		return;	if(root->leftChild != NULL)//這個要復制的節點的左孩子不是空	{		leftLink = copyTree(root->leftChild);//復制這個左孩子	}else		leftLink = NULL;	if(root->rightChild != NULL)//這個要復制的節點的左孩子不是空	{		rightLink = copyTree(root->rightChild);//復制這個左孩子	}else		rightLink = NULL;	//為新生成的節點申請空間	if((p = (BTREE *)calloc(sizeof(BTREE), 1)) == NULL){		printf("申請空間失敗");	}	p->leftChild = leftLink;	p->rightChild = rightLink;	p->value = root->value;	return p;}
3 求葉子節點數
void getTreeCount(BTREE *root, int *pcount){	if(root == NULL){		return;	}	if(root->leftChild == NULL && root->rightChild == NULL){		(*pcount)++;	}//葉子節點的左孩子和右孩子都是空	getTreeCount(root->leftChild, pcount);	getTreeCount(root->rightChild, pcount);}