二元树.cpp

二元树的建立和遍历 c语言实现 比较简单

#include<iostream.h>
#define Max 100
typedef struct{
	void* elem[Max];
	int top;
} stack;
int empty(stack s);
struct node* pop(stack &s);
void push(void* x,stack &s);
struct node {
	struct node *lchild;
    struct node *rchild;
	char data;
};
typedef struct node * betree;
void creatbt1(betree & t);//先根递归建立
void creatbt2(betree & t,stack &s);//先根非递归建立
void  forder10(betree & t);//先根递归
void  forder11(betree & t,stack &s);//先根非递归
void  inorder20(betree & t);//中根递归
void  inorder21(betree & t,stack &s);//中根非递归
void  porder30(betree & t);//后根递归
void  porder31(betree & t,stack &s);//后根非递归
//二元树的建立与遍历
void main()
{
    int num;
    betree root;
    stack s;
	s.top=0;
	cout<<"please enter the number:(建立函数1，先根递归2，先根非递归)\n";
	cin>>num;
	cout<<"先根输入树：\n";
	if(num==1)
 	  creatbt1(root);
	else
     creatbt2(root,s);
	cout<<"先根递归\n";
	forder10(root);
     cout<<endl;
	cout<<"先根非递归\n";
    forder11(root,s);
     cout<<endl;
	cout<<"中根递归\n";
	inorder20(root);
      cout<<endl;
	cout<<"中根非递归\n";
    inorder21(root,s);
     cout<<endl;
	cout<<"后根递归\n";
    porder30(root);

       cout<<endl;
	cout<<"后根非递归\n";
    porder31(root,s);
    cout<<endl; 
}
void creatbt1(betree & t)
{
	char ch;
	cin>>ch;
	if(ch=='#')t=NULL;
	else
	{
	   	t=new node;
		t->data = ch;
        creatbt1(t->lchild);
        creatbt1(t->rchild);
	}
}
void creatbt2(betree & t,stack &s)
{    
	 int m=0,n=0;
	 betree p=t,*p1,p2=t;
	 char ch;
     push(0,s);
	 while(p2!=NULL)
	 {
	     cin>>ch;
	     if(ch!='#')//建立左树
		 {   
             p=new node;
		     p->data = ch;
             p->rchild=NULL;
		     if(n==0)
			 {
			     t=p;
		         n=1;
			 } 
			 else
				 *p1=p;
		     push(p,s);		    
		     p1=&p->lchild;
		 }
	     else//建立右树
		 {
			 *p1=NULL;
			 p2=pop(s);
			 p1=&p2;
             cin>>ch;
			 while(m==0 && *p1!=NULL)
			 {
		          if(ch!='#')
				  {
                     p=new node;
		             p->data = ch;
     				 push(p,s);
                     p->rchild=NULL;
					 (*p1)->rchild=p;
					 p1=&p->lchild;
                     m=1;
				  }
				  else
				  {
                    (*p1)->rchild=NULL; 
                    p2=pop(s);
					p1=&p2;
					if(p2!=NULL)
                    cin>>ch;
				  }
			 }
			 m=0;
		 }
	 }
}
void  forder10(betree & t)
{
	if(t!=NULL)
	{
	   	cout<<t->data;
        forder10(t->lchild);//建立左树
        forder10(t->rchild);//建立右树
	}
	else
		cout<<'#';
}
void  forder11(betree & t,stack &s)
{
     betree p=t;
	 push(0,s);
	 while(p!=NULL)
     {
		 cout<<p->data;
		 if(p->rchild!=NULL)
			 push(p->rchild,s);
		 if(p->lchild!=NULL)
			 p=p->lchild;
		 else
			p=pop(s);
	 }
}
void  inorder20(betree & t)
{
	if(t!=NULL)
	{	   	
        inorder20(t->lchild);
        cout<<t->data;
        inorder20(t->rchild);
	}
    else
		cout<<'#';
}
void  inorder21(betree & t,stack &s)
{
	 int n=1;//标志
     betree p=t;
	 push(0,s);
	 while(p!=NULL)
     {
		 push(p,s);
		 if(p->lchild!=NULL)
		 {			 
			 p=p->lchild;
		 }
		 else
		 {  
             if(p->rchild!=NULL)
			 {
				   pop(s); 
				   cout<<p->data;
			       p=p->rchild;
			 }
		     else
			 {
				 while(p!=NULL&&p->rchild==NULL&&n==1)
				 {
			         p=pop(s);
				     if(p!=NULL)
					 {
                         cout<<p->data;
		                 if(p->rchild!=NULL)
						 {
			               p=p->rchild;
						   n=0;
						 }
						  
					 }
				 }
				 n=1;
			 }

		 }
	 }
}
void  porder30(betree & t)
{
	if(t!=NULL)
	{	   	
        porder30(t->lchild);     
        porder30(t->rchild);
		cout<<t->data;
	}
    else
		cout<<'#';
}
void  porder31(betree & t,stack &s)
{
	 int n=1,m=1;
     betree p=t,p1;
	 push(0,s);
     while(p!=NULL)
     {
		 if(p->lchild!=NULL)
		 {   
			 p1=p;
			 push(p,s);
             p=p->lchild;
		 }
		 else
		 {
			 while(n!=0&&p!=NULL)
			 {
		          if(p->rchild!=NULL)
				  {   
					  push(p,s);
                      p1=p->rchild;
                      p->rchild=NULL;
					  p=p1;
			          n=0;
				  }
		          else
				  {
				         cout<<p->data;
                          p=pop(s);
				  }
			 }
			 n=1;
		 }
	 }
	 
}
int empty(stack s)//判断栈是否为空
{
	if(s.top < 1)
		return 1;
	else 
		return 0;
}
struct node* pop(stack &s)//压栈
{
    struct node* p;
	if(empty(s))
		cout<<"error\n";
	else 
	{
        p=(struct node*)s.elem[s.top];
		s.top = s.top-1;
	}
	return p;
}
void push(void* x,stack &s)//弹栈
{
	if(s.top == Max-1)
		cout<<"error2\n";
	else 
	{
	   	s.top = s.top+1;
		s.elem[s.top] = x;
	}
}