#include "iostream.h"
typedef char TelemType;

typedef struct BiTNode{
       TelemType data;
      struct BiTNode *lchild,*rchild;    /*左右孩子指針*/
   }BiTNode;
//按先序遍歷得到的字符串建立二叉鏈表
BiTNode *createbtree()
{BiTNode *t;
	TelemType ch;
	cin>>ch;
if(ch=='#') return 0;
else
{t=new BiTNode;
t->data=ch;
t->lchild=createbtree();
t->rchild=createbtree();
	}
return t;
}
//先序遍歷
void preorder(BiTNode *t)
{if(t!=0)
{cout<<t->data<<"  ";
preorder(t->lchild);
preorder(t->rchild);
}
}
//中序遍歷
void inorder(BiTNode *t)
{if(t!=0)
{
inorder(t->lchild);
cout<<t->data<<"  ";
inorder(t->rchild);
}
}
//后序遍歷
void postorder(BiTNode *t)
{if(t!=0)
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data<<"  ";
}
}
//求結點數
void nodecount(	BiTNode  *t,int &k)
{
	if(t!=0)
	{
	 k++;
	 nodecount(t->lchild,k);
     nodecount(t->rchild,k);
	}

}
//求度為2的結點數
void twocount(	BiTNode  *t,int &k)
{
	if(t!=0)
	{
	if((t->lchild!=0) && (t->rchild!=0)) k++;
	 twocount(t->lchild,k);
     twocount(t->rchild,k);
	}
}
//求二叉樹中的葉子個數
void leafcount(BiTNode *t,int &k)
{
	if(t!=0)
	{
        if((t->lchild==0) && (t->rchild==0)) k++;
	 leafcount(t->lchild,k);
         leafcount(t->rchild,k);
	}

}
//求二叉樹中的葉子數和結點總數。
void count(BiTNode *t,int &k,int &m)
{
	if(t!=0)
	{
	    m++;
		if((t->lchild==0) && (t->rchild==0)) k++;
	 count(t->lchild,k,m);
     count(t->rchild,k,m);
	}

}
//查找值為x的結點，若存在，返回其指針
BiTNode *locate(BiTNode *bt,TelemType x)
   {BiTNode *p;
    if(bt==0) return 0;
	if(bt->data==x)return bt;
	if(bt->lchild !=0) 
	{p=locate(bt->lchild,x);
	if(p!=0) return p;
	}
  if(bt->rchild !=0)
  {p=locate(bt->rchild,x);
	if(p!=0) return p;
	}
	 return 0;
}

/*在二叉樹bt中，將y插入到二叉樹，使之成為結點x的左孩子*/
BiTNode *btreeinsertL(BiTNode *bt,TelemType x,TelemType y)
     {
      BiTNode *p,*q;
      if (bt==0)
       {cout<<"\n插入出錯\n";
         return NULL;
       }
      p=new BiTNode;
      p->data=y;
      p->lchild=NULL;
      p->rchild=NULL;
      q=locate(bt,x);

	  if (q->lchild==NULL) q->lchild=p;
      else {p->lchild=q->lchild;
           q->lchild=p;
          }
      return bt;
}
/*在二叉樹bt中，將y插入到二叉樹，使之成為結點x的右孩子*/
BiTNode *btreeinsertR(BiTNode *bt,TelemType x,TelemType y)
     {
      BiTNode *p,*q;
      if (bt==0)
       {cout<<"\n插入出錯\n";
         return NULL;
       }
      p=new BiTNode;
      p->data=y;
      p->lchild=NULL;
      p->rchild=NULL;
      q=locate(bt,x);

	  if (q->rchild==NULL) q->rchild=p;
      else {p->rchild=q->rchild;
           q->rchild=p;
          }
      return bt;
}
 /*在二叉樹bt中刪除結點x的左子樹*/
/*
BiTNode  *DeleteL(BiTNode *bt,TelemType x)
    {
      BiTNode  *p,*q;
	  p=locate(bt,x);
    if(p->lchild!=0)
	{q=p->lchild;
	if(q->lchild==0&&q->rchild==0) //當p為非葉子結點時，這樣刪除僅釋放了所刪子樹根結點的空間，
	  {p->lchild==0;delete q; }
	  else if(q->lchild!=0&&q->rchild==0)
	  { p->lchild=q->lchild;delete q;}
      else    
	   cout<<"無法刪除!"<<endl;
	   //若要刪除子樹分支中的結點，需用后面介紹的遍歷操作來實現。 
      return bt;
}
*/
//輸出二叉樹（向左旋轉90度）
void printbtree(BiTNode  *t,int level)
{ if(t!=0)
 printbtree(t->rchild,level+1);
  if(level!=0)
  { for(int i=0;i<6*(level-1);i++) cout<<"  ";
  cout<<"----";
  }
  cout<<t->data<<endl;
  printbtree(t->lchild ,level+1);
}

//求二叉樹深度
int btreedepth(BiTNode  *t)
{int i,j;
if(t==0) return 0;
else
{i=btreedepth(t->lchild);
j=btreedepth(t->rchild);
return (i>j?i:j)+1;
}
}
//試編寫算法判斷兩棵二叉樹是否等價。若二叉樹T1和T2等價，則T1和T2都是空的二叉樹；或T1和T2的根結點的值是相同的，并且T1的左子樹和T2的右子樹是等價的，T1的右子樹與T2的右子樹是等價的。
int tt(BiTNode  *t1,BiTNode  *t2)
{
if(t1==0&&t2==0) return 1;
else
{ if(t1==0||t2==0) return 0;
  else
   if(t1->data==t2->data)
    return tt(t1->lchild,t2->lchild) && tt(t1->rchild,t2->rchild) ;
}
}

void main()
{ int  x=0;
  int z,y;
   BiTNode  *t1,*t=0;
t1=createbtree(); 
printbtree(t1,x);
leafcount(t1,z,y);
cout<<z<<"  "<<y<<endl;
/*
preorder(t1);
cout<<endl;
inorder(t1);
cout<<endl;
postorder(t1);
cout<<endl;
twocount(t1,x);
cout<<"du is 2=  "<< x<<endl;
//t1=btreeinsertL(t1,'c','r');
t1=btreeinsertR(t1,'e','r');

preorder(t1);)*/
}