#include "stdio.h"
#include "malloc.h"
#define MaxSize 100
typedef char ElemType;

typedef struct node
{
	ElemType data;
	struct node *lchild;
	struct node *rchild;
}BTNode;
void CreateBTNode(BTNode * &b,char *str)
{
	BTNode * St[MaxSize], * p;
	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)  //若尚未建立根节点
				b=p;     //*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)
{
	BTNode *p;
	if(b==NULL)
		return b;
	else 
	{
		p=FindNode (b->lchild,x);
			if(p!=NULL)
				return p;
			else
				return FindNode(b->rchild,x);
				}
}


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(")");
		}
	}
}



BTNode  *LchildNode(BTNode *p)
{
	return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
	return p->rchild;
}


int BTNodeHeight(BTNode *b)
{
	int lchild,rchild;
	if(b==NULL)return(0);   //空树的高度为0
	else
	{
		lchild=BTNodeHeight(b->lchild);   //求左子树的高度为lchildh
		rchild=BTNodeHeight(b->rchild);   //求右子树的高度为rchildh
		return(lchild>rchild)?(lchild+1):(rchild+1);
	}
}

int main()
{
	BTNode *b,*p,*lp,*rp;
	BTNode *root=NULL;
	char btstr[]="A(B(D(,G)),C(E,F))";
	CreateBTNode(root,btstr);
	printf("\n");
	DispBTNode(b);
	p=FindNode(b,'D');
	LchildNode(p);
	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");
	BTNodeHeight(b);
	printf("二叉树b的高度:%d\n",BTNodeHeight(b));
}