tree.cpp

平衡二元查找树 是用链表实现的 课程设计内容

#include <iostream>
#define max 100
using namespace std;
typedef struct {char parent,data,tag;}bnode;
typedef struct node{char data;                                      //建立二元树的节点结构
                    node *lchild,*rchild;} *btree;
//定义队列
typedef struct {btree ele[max];
				int front,rear;}squeue;
typedef char datatype;
struct st{ btree ch;
		   st *next;};
btree creat(void);
void pretree(btree bt);
void midtree(btree bt);
void postree(btree bt);
void pretree1(btree bt);
 void midtree1(btree bt);
 void  postree1(btree bt);
st * push(btree c,st *s);
 btree pop(st * &s);
int main (void)
{ btree tree;
  cout<<"请输入结点：包括它本身的值（用字母表示），  父节点的值（用字母表示），  它是左儿子（l）还是右儿子（r）,无（#）"<<endl;
  cout<<"’###‘：表结束"<<endl;
  tree= creat();
  cout<<"前根遍历（递归）： ";
   pretree(tree);
   cout<<endl;
   cout<<"（非递归）：       ";
   pretree1(tree);
   cout<<endl;
   cout<<"中根遍历（递归）： ";
   midtree(tree);
   cout<<endl;  
   cout<<"（非递归）：       ";
   midtree1(tree );
   cout<<endl;
  cout<<"后根遍历（递归）： ";
   postree(tree);
   cout<<endl;
   cout<<"（非递归）：       ";
   postree1(tree );
   cout<<endl;
   return 0;
}

//建立一株二元树
 btree creat(void)
{  squeue q;
   bnode p;
   btree root,s;
   root=new node;
   root=NULL;
   q.front=q.rear=0;
   cin>>p.data>>p.parent>>p.tag;
   while(p.data!='#')
   { s=new node;
     s->data=p.data;
	 s->lchild=s->rchild=NULL;
	 q.ele[q.rear]=s;
	 q.rear++;
	 if(p.parent=='#')                       //	确定根结点
		 root=s;
	 else                                    //查找父结点
	 { for(q.front=0;q.front<=q.rear&&q.ele[q.front]->data!=p.parent;)
	        { q.front++;} 
	   if(q.ele[q.front]->data==p.parent)
	     {  if(p.tag=='l')
		      q.ele[q.front]->lchild=s;
		    else
			 q.ele[q.front]->rchild=s;
	     }
	   else
		  cout<<"输入有误！"<<endl;
	  }
	  cin>>p.data>>p.parent>>p.tag;
      }
   return root;
}
//先根遍历(递归算法)
 void pretree(btree bt)
 { if(bt!=NULL)
      { cout<<bt->data;
        pretree(bt->lchild);
        pretree(bt->rchild);
       }
 }
 //中根遍历(递归算法)
 void midtree(btree bt)
 { if(bt!=NULL)
      {  midtree(bt->lchild);
		cout<<bt->data;
        midtree(bt->rchild);
       }
 }
//后根遍历(递归算法)
 void postree(btree bt)
 { if(bt!=NULL)
      {  postree(bt->lchild);
		postree(bt->rchild);
		 cout<<bt->data;
       }
 }
//压栈
 st * push(btree c,st *s)
 {   st *p=new st;
	 s->ch=c;
     p->next=s;
	 p->ch=NULL;
	return p; 
 }
 //弹栈
 btree pop(st * &s)
 { s=s->next;
  if(s!=NULL)
     return s->ch;
  else return NULL;
 }
 //先根遍历（非递归算法)
 void pretree1(btree bt)
 {   st *s=new st;
     btree b=bt;
	   s->next=NULL;
	 while(b!=NULL)
		 { cout<<b->data;
	       if(b->rchild!=NULL)
		      s=push(b->rchild,s);
		    if(b->lchild!=NULL)
				b=b->lchild;
			else
				b=pop(s);
		 }
		 delete s;
 }
 //中根遍历（非递归算法)
 void midtree1(btree bt)
 {   st *s=new st;
     btree a=new node;
	 btree b=bt;
	  s->next=NULL;
	 while(b!=NULL&&a!=NULL)
		 { while(b->lchild!=NULL)
			 { s=push(b,s);
		        b=b->lchild;
			 }
			cout<<b->data;
			  if(b->rchild!=NULL)
                 b=b->rchild;
				else
				   {a=pop(s);
				    while(a!=NULL)
					{cout<<a->data;
					if(a->rchild==NULL)
					   a=pop(s);
					else
						{b=a->rchild;
						break;}
					}
					}
		 }
		 delete s;
 }
//后根遍历
void  postree1(btree bt)
{    st *s=new st;
     btree x=new node,a=new node;
	 btree b=bt;
	 s->next=NULL;
   while(b!=NULL)
   {   while(b->lchild!=NULL)
   {    s=push(b,s);
        b=b->lchild;
   }
        while(b!=NULL&&b->rchild==NULL)
		{ cout<<b->data;
         x=b;
		 b=pop(s);
		 while(b!=NULL&&b->rchild==x)
		 {	cout<<b->data;
		    x=b;
		    b=pop(s);
		 }
		}
	    if(b==NULL)
		  break;
		if(b->rchild!=NULL)
		{ s=push(b,s);
		  b=b->rchild;
		}
		}
   delete a,x;
}