#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct node{	ElemType data;				//數據元素	struct node *lchild;		//指向左孩子	struct node *rchild;		//指向右孩子} BTNode;void CreateBTNode(BTNode *&b,char *str)		//由str串創建二叉鏈{	BTNode *St[MaxSize],*p=NULL;	int top=-1,k,j=0;	char ch;	b=NULL;				//建立的二叉樹初始時為空	ch=str[j];	while (ch!='/0')	//str未掃描完時循環	{   	   	switch(ch)		{		case '(':top++;St[top]=p;k=1; break;		//為左節點		case ')':top--;break;		case ',':k=2; break;                      	//為右節點		default:p=(BTNode *)malloc(sizeof(BTNode));			p->data=ch;p->lchild=p->rchild=NULL;		         	if (b==NULL)                    //p指向二叉樹的根節點						b=p;					else  							//已建立二叉樹根節點					{						switch(k)						{						case 1:St[top]->lchild=p;break;						case 2:St[top]->rchild=p;break;						}					}		}		j++;		ch=str[j];	}}BTNode *FindNode(BTNode *b,ElemType x)	//返回data域為x的節點指針{	BTNode *p;	if (b==NULL)	     return NULL;	else if (b->data==x)	     return b;	else	{		p=FindNode(b->lchild,x);		if (p!=NULL)			return p;		else			return FindNode(b->rchild,x);	}}BTNode *LchildNode(BTNode *p)	//返回*p節點的左孩子節點指針{    return p->lchild;}BTNode *RchildNode(BTNode *p)	//返回*p節點的右孩子節點指針{    return p->rchild;}int BTNodeDepth(BTNode *b)	//求二叉樹b的深度{   	int lchilddep,rchilddep;   	if (b==NULL)		return(0); 							//空樹的高度為0   	else	{		lchilddep=BTNodeDepth(b->lchild);	//求左子樹的高度為lchilddep	  	rchilddep=BTNodeDepth(b->rchild);	//求右子樹的高度為rchilddep		return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);   	}}void DispBTNode(BTNode *b)	//以括號表示法輸出二叉樹{	if (b!=NULL)	{		PRintf("%c",b->data);		if (b->lchild!=NULL || b->rchild!=NULL)		{			printf("(");			DispBTNode(b->lchild);			if (b->rchild!=NULL) printf(",");			DispBTNode(b->rchild);			printf(")");		}	}}int BTWidth(BTNode *b)  //求二叉樹b的寬度{	struct	{		int lno;		//節點的層次編號		BTNode *p;		//節點指針	} Qu[MaxSize];		//定義順序非循環隊列	int front,rear;							//定義隊首和隊尾指針	int lnum,max,i,n;	front=rear=0;							//置隊列為空隊    if (b!=NULL)	{		rear++;		Qu[rear].p=b;						//根節點指針入隊		Qu[rear].lno=1;						//根節點的層次編號為1		while (rear!=front)					//隊列不為空		{			front++;			b=Qu[front].p;					//隊頭出隊			lnum=Qu[front].lno;			if (b->lchild!=NULL)			//左孩子入隊			{				rear++;				Qu[rear].p=b->lchild;				Qu[rear].lno=lnum+1;			}			if (b->rchild!=NULL)			//右孩子入隊			{				rear++;				Qu[rear].p=b->rchild;				Qu[rear].lno=lnum+1;			}		}		max=0;lnum=1;i=1;		while (i<=rear)		{			n=0;			while (i<=rear && Qu[i].lno==lnum)			{				n++;i++;			}			lnum=Qu[i].lno;			if (n>max) max=n;		}		return max;	}	else		return 0;}int Nodes(BTNode *b)	//求二叉樹b的節點個數{	int num1,num2;    if (b==NULL)		return 0;    else if (b->lchild==NULL && b->rchild==NULL)		return 1;    else    {        num1=Nodes(b->lchild);        num2=Nodes(b->rchild);        return (num1+num2+1);	}}int LeafNodes(BTNode *b)	//求二叉樹b的葉子節點個數{	int num1,num2;    if (b==NULL)		return 0;    else if (b->lchild==NULL && b->rchild==NULL)		return 1;    else    {        num1=LeafNodes(b->lchild);        num2=LeafNodes(b->rchild);        return (num1+num2);	}}void DestroyBTNode(BTNode *&b){	if (b!=NULL)	{		DestroyBTNode(b->lchild);		DestroyBTNode(b->rchild);		free(b);	}}int main(){	BTNode *b,*p,*lp,*rp;;	CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");	printf("二叉樹的基本運算如下:/n");	printf("  (1)輸出二叉樹:");DispBTNode(b);printf("/n");	printf("  (2)H節點:");	p=FindNode(b,'H');	if (p!=NULL)	{	lp=LchildNode(p);		if (lp!=NULL)			printf("左孩子為%c ",lp->data);		else			printf("無左孩子 ");		rp=RchildNode(p);		if (rp!=NULL)			printf("右孩子為%c",rp->data);		else			printf("無右孩子 ");	}	printf("/n");	printf("  (3)二叉樹b的深度:%d/n",BTNodeDepth(b));	printf("  (4)二叉樹b的寬度:%d/n",BTWidth(b));	printf("  (5)二叉樹b的節點個數:%d/n",Nodes(b));	printf("  (6)二叉樹b的葉子節點個數:%d/n",LeafNodes(b));	printf("  (7)釋放二叉樹b/n");	DestroyBTNode(b);	return 0;}
運行結果：