例6_5.cpp

《数据结构（C++描述）》-李根强-源代码

//由二叉树的前序序列和中序序列建立该二叉树
#include<iostream.h>
typedef char elemtype;
struct  bitree
{  
  elemtype data;
   bitree *lchild,*rchild;
};
elemtype pre[100],ind[100];//存放前序序列和中序序列的一维数组

bitree *create(int l1,int h1,int l2,int h2)
//前序序列存入PRE[l1]到PRE[h1]中,中序序列存入IND[l2]到IND[h2]中
{    bitree *t;
	if (h2-l2!=h1-l1)      return  NULL;//cout<<"input error";
    else{ if(l1>h1)   t=NULL;        //建空树
            else
           {  t=new bitree;  t->data=pre[l1];
           int s=l2;
           while((s<h2)&&(pre[l1]!=ind[s]))
           s++;                 //找中序序列中根结点
           if(ind[s]!=pre[l1])   cout<<"input error";
           else 
              {t->lchild=create(l1+1,l1+s-l2,l2,s-1);
               t->rchild=create(l1+s-l2+1,h1,s+1,h2);
             }
              }
             }
             return  t;
       }
//前序遍历二叉树的非递归算法如下：
void preorder1(bitree *root)
{ bitree *p,*s[100];
  int top=0;  //top为栈顶指针
  p=root;
  while((p!=NULL)||(top>0))
  {       while(p!=NULL)
            {cout<<p->data<<" ";
               s[++top]=p;
			   p=p->lchild;
            }
    p=s[top--];
	p=p->rchild;
  } 
}

//中序遍历二叉树的非递归算法如下：
void inorder1( bitree *root)
{ bitree *p,*s[100];    //s为一个栈，top为栈顶指针
  int top=0;
  p=root;
  while((p!=NULL)||(top>0)) 
  {   while(p!=NULL)
       {s[++top]=p;p=p->lchild;}
   {p=s[top--];
   cout<<p->data<<" ";
   p=p->rchild;
  }
  }
}
//后序遍历二叉树的非递归算法如下：
void postorder1( bitree *root)
{  bitree *p,*s1[100];             //s1栈存放树中结点
   int s2[100],top=0,b;           //s2栈存放进栈标志
   p=root;
   do
   {  while(p!=NULL)
        {s1[top]=p;s2[top++]=0;    //第一次进栈标志为0
         p=p->lchild;}
       if(top>0)
	   {b=s2[--top];
	   p=s1[top];
	   if(b==0)
	   {s1[top]=p;s2[top++]=1;  //第二次进栈标志为0

	   p=p->rchild;}
	   else
	   {cout<<p->data<<" ";
	   p=NULL;
	   }
	   }
   }while(top>0);
}


void main()
{ int n;
cout<<"请输入二叉树的结点数目"<<endl;
cin>>n;
cout<<"请输入前序序列"<<endl;
for(int i=1;i<=n;i++) cin>>pre[i];
cout<<"请输入中序序列"<<endl;
for( i=1;i<=n;i++) cin>>ind[i];
bitree *t=create(1,n,1,n);
cout<<"前序序列为:"<<endl;
preorder1(t);
cout<<endl<<"中序序列为:"<<endl;
inorder1(t);
cout<<endl<<"后序序列为:"<<endl;
postorder1(t);
}