bianli.cpp

数据结构中树的遍历

#include "iostream.h"
#include "math.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 preorder1(BiTNode *t)
{BiTNode *s[100];
int top=0;
while(t!=0||top!=0)
{ while(t!=0) {cout<<t->data<<"  ";s[++top]=t;t=t->lchild;}
if(top!=0) {t=s[top--];t=t->rchild;}
}
}
//非递归中序遍历
void inorder1(BiTNode *t)
{BiTNode *s[100];
int top=0;
while(t!=0||top!=0)
{ while(t!=0) {s[++top]=t;t=t->lchild;}
if(top!=0) {t=s[top--];cout<<t->data<<"  ";t=t->rchild;}
}
}
//非递归后序遍历
void postorder1(BiTNode *t)
{typedef struct 
{BiTNode *t;int tag;
}stack;
stack s[100];
int top=0;
while(t!=0||top!=0)
{ while(t!=0) {s[++top].t=t;s[top].tag=0;t=t->lchild;}
while(top&&s[top].tag==1) cout<<s[top--].t->data<<"  ";
if(top!=0) {s[top].tag=1;t=s[top].t->rchild;}
}
}

//先序遍历
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,若存在返回指向x的指针；否则返回0
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;
}
//删除二叉树
void deletetree(BiTNode *t)
{BiTNode *p;
	if(t!=0)
	{
deletetree(t->lchild);
deletetree(t->rchild);
p=t;delete p;
}
}

 /*在二叉树bt中删除结点x的左子树*/
void DeleteL(BiTNode *bt,TelemType x)
    {
      BiTNode  *p,*q;
	  p=locate(bt,x);
    if(p->lchild!=0)
	{q=p;p=p->lchild;
	q->lchild=0;
	deletetree(p);
	}
	else    
	   cout<<"无法删除!"<<endl;
	   //若要删除子树分支中的结点，需用后面介绍的遍历操作来实现。 
     
}

//输出二叉树（向左旋转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 level(BiTNode *t)
{int i,j;
	if(t==0) return 0;
else
{ i=level(t->lchild);j=level(t->rchild);
return (i>j?i:j)+1;}
}
//交换二叉树的左右子树
void changeB(BiTNode *t)
{ if(t!=0)
{changeB(t->lchild);
changeB(t->rchild);
BiTNode *p;
p=t->lchild;
t->lchild=t->rchild;
t->rchild=p;
}
}
//试编写算法判断两棵二叉树是否等价。若二叉树T1和T2等价，则T1和T2都是空的二叉树；
//或T1和T2的根结点的值相同，并且T1的左子树与T2的左子树是等价的，T1的右子树与T2的右子树是等价的。
int liketree(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 liketree(t1->lchild,t2->lchild) && liketree(t1->rchild,t2->rchild) ;
}
//以二叉链表作为存储结构，写一个复制二叉树的算法
BiTNode *btreecopy(BiTNode *t)
{BiTNode *p;
if(t!=0)
{p=new BiTNode;
p->data=t->data;
p->lchild=btreecopy(t->lchild);
p->rchild=btreecopy(t->rchild);
return p;
}
else
   return 0;
}
//以二叉链表作为存储结构，写出在二叉树中求值为x的结点在树中层数的算法。
void treedepth(BiTNode *t,TelemType x,int &h,int depth)
{if(t==0) h=0;
else if(t->data==x) h=depth;
else 
 {treedepth(t->lchild,x,h,depth+1);
      if(h==-1) treedepth(t->rchild,x,h,depth+1); 
 }
}
void main()
{ int  x=0,y;
	BiTNode  *t1,*t2,*t=0;
t1=createbtree(); 
int s=-1;
treedepth(t1,'b',s,1);
cout<<s<<endl;

/*
//t2=createbtree();
t2=btreecopy(t1);
if(liketree(t1,t2)) cout <<"same1"<<endl;
else cout<<"not name"<<endl;
//DeleteL(t1,'a');
//changeB(t1);
//preorder1(t1);cout<<endl;
printbtree(t1,x);
printbtree(t2,x);

/*
inorder1(t1);cout<<endl;
postorder1(t1);cout<<endl;


//y=level(t1);
//cout<<"level is "<<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);)
*/
}