#include "iostream.h"
typedef char TelemType;
#define MAXSIZE 50
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<<"  ";
}
}
//求結(jié)點(diǎn)數(shù)（先序遍歷）
void nodecount(	BiTNode  *t,int &k)
{
	if(t!=0)
	{
	 k++;
	 nodecount(t->lchild,k);
         nodecount(t->rchild,k);
	}

}
//求度為2的結(jié)點(diǎn)數(shù)
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);
	}
}
//求二叉樹中的葉子個(gè)數(shù)
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);
	}

}
//查找結(jié)點(diǎn)值為x的結(jié)點(diǎn)，返回結(jié)點(diǎn)的指針
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;
}
//查找x的雙親、孩子
void locatechild(BiTNode *bt,TelemType x)
   {
    if(bt==0) {cout<<"結(jié)點(diǎn)不存在!"<<endl; return;}
   if(bt->data==x)
   { //cout<<"雙親是："<<bt->parent->data<<endl;
       if(bt->lchild) cout<<"左孩子是："<<bt->lchild->data<<endl;
       else cout<<"無左孩子";
      if(bt->rchild) cout<<"右孩子是："<<bt->rchild->data<<endl;
      else cout<<"無右孩子";
      return;  }
   if(bt->lchild!=0)    locatechild(bt->lchild,x);
    if(bt->rchild!=0)
    locatechild(bt->rchild,x);
}
/*在二叉樹bt中，將y插入到二叉樹，使之成為結(jié)點(diǎn)x的左孩子*/
BiTNode *btreeinsertL(BiTNode *bt,TelemType x,TelemType y)
     {
      BiTNode *p,*q;
      if (bt==0)
       {cout<<"\n插入出錯(cuò)\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插入到二叉樹，使之成為結(jié)點(diǎn)x的右孩子*/
BiTNode *btreeinsertR(BiTNode *bt,TelemType x,TelemType y)
     {
      BiTNode *p,*q;
      if (bt==0)
       {cout<<"\n插入出錯(cuò)\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中刪除結(jié)點(diǎn)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) //當(dāng)p為非葉子結(jié)點(diǎn)時(shí)，這樣刪除僅釋放了所刪子樹根結(jié)點(diǎn)的空間，
	  {p->lchild==0;delete q; }
	  else if(q->lchild!=0&&q->rchild==0)
	  { p->lchild=q->lchild;delete q;}
      else    
	   cout<<"無法刪除!"<<endl;
	   //若要?jiǎng)h除子樹分支中的結(jié)點(diǎn)，需用后面介紹的遍歷操作來實(shí)現(xiàn)。 
      return bt;
}
*/
//輸出二叉樹（向左旋轉(zhuǎn)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);
}
}
//層次遍歷
void LevelOrder(BiTNode *t)
{

BiTNode *p,*qu[MAXSIZE];
int front ,rear;
front=-1;
rear=0;
qu[rear]=t;
while(front!=rear)
{
   front=(front+1)%MAXSIZE;
   p=qu[front];
   cout<<p->data;
  if(p->lchild!=0)
  {rear=(rear+1)%MAXSIZE;
  qu[rear]=p->lchild;
  }
 if(p->rchild!=0)
 {rear=(rear+1)%MAXSIZE;
 qu[rear]=p->rchild;
 }
}
}
//求二叉樹的葉子數(shù)和結(jié)點(diǎn)數(shù)
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);
	}

}
//
void main()
{ int  x=0;
int m=0,n=0;
	BiTNode  *t1;
t1=createbtree(); 
printbtree(t1,x);
//count(t1,m,n);
//cout<<m<<"node :"<<n<<endl;
//locatechild(t1,'b');
//cout<<endl;
/*cout<<"level:"<<endl;
LevelOrder(t1);
cout<<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');
*/
cout<<"先序遍歷："<<endl;
preorder(t1);
cout<<"中序遍歷："<<endl;
inorder(t1);
cout<<"后序遍歷："<<endl;
postorder(t1);

}