二叉树.cpp

用各种方法遍历二叉树 建立二叉链表 前序 中 后 递归非递归

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

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

void main()
{ int  x=0;
	BiTNode  *t1,*t=0;
t1=createbtree(); 
printbtree(t1,x);
/*
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);)*/
}