二叉树.cpp

二叉树的建立

#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<<"  ";
}
}
//求结点数（先序遍历）
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);
	}

}
//查找结点值为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;
}
//查找x的双亲、孩子
void locatechild(BiTNode *bt,TelemType x)
   {
    if(bt==0) {cout<<"结点不存在!"<<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插入到二叉树，使之成为结点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);
}
}
//层次遍历
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;
 }
}
}
//求二叉树的叶子数和结点数
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);

}