#include <stdio.h>
#include <stdlib.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=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{
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;
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 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)
{
return p->lchild;
}

btnode * rchildnode(btnode *p)
{
return p->rchild;
}

int btnodedepth(btnode *b)
{
int lchilddep,rchilddep;
if(b==NULL)
return 0;
else
{
lchilddep=btnodedepth(b->lchild);
rchilddep=btnodedepth(b->rchild);
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 nodes(btnode *b)
{
int n1,n2;
if(b==NULL)
return 0;
else
{
n1=nodes(b->lchild);
n2=nodes(b->rchild);
return(n1+n2+1);
}
}

int leafnodes(btnode *b)
{
int n1,n2;
if(b==NULL)
return 0;
else if(b->lchild==NULL&&b->rchild==NULL)
return 1;
else
{
n1=leafnodes(b->lchild);
n2=leafnodes(b->rchild);
return(n1+n2);
}
}

int main()
{
btnode *b,*p,*lp,*rp;
createbtnode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
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",nodes(b));
printf("(5)二叉树b的叶子结点个数:%d\n",leafnodes(b));
return 0;
}