#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));
}