erchashu.cpp

1、 本演示程序实现对二叉树的先序、中序、后序三种遍历。 2、 二叉树的元素为所有字符集合。 3、 演示程序以人机对话方式执行

#include<iostream.h>
typedef char elemtype;
struct bitree
{
	elemtype data;
	bitree *lchild,*rchild;
};
bitree *create()
{  bitree *root,*s,*q[100];
int front=1,rear=0;
char ch;
root=NULL;
cout<<"请输入结点值，（‘，’为虚结点，‘#’结束）"<<endl;
cin>>ch;
while(ch!='#')
{s=NULL;
 if (ch!=',')
 {s=new bitree;
  s->data=ch;
  s->lchild=NULL;
  s->rchild=NULL;
 }
    rear++;                         //进队
	q[rear]=s;
	if (rear==1) root=s;
	else
	{if((s!=NULL)&&(q[front]!=NULL))
	  {if(rear%2==0) q[front]->lchild=s;
	   else q[front]->rchild=s;}
	   if(rear%2==1) front++;        //出队
	   }
	cin>>ch;}
return root;
}
void preorderl(bitree *root)         //先序遍历
{  bitree *p,*s[100];                //s为堆栈
   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 inorderl(bitree *root)           //中序遍历
{  bitree *p,*s[100];
   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 postorderl(bitree *root)         //后序遍历
{  bitree *p,*s1[100];
   int s2[100],top=0,b;
   p=root;
   do
   { while(p!=NULL)
     {s1[top]=p;s2[top++]=0;
      p=p->lchild;}
    if(top>0)
	   {b=s2[--top];
	    p=s1[top];
		if(b==0)
		   {s1[top]=p;s2[top++]=1;
		    p=p->rchild;}
		else
		   {cout<<p->data<<" ";
		    p=NULL;
		}
	}
   }while(top>0);
}
void main()
{  bitree *root;
   root=create();                      //建立二叉链表
   cout<<"先序遍历的结果"<<endl;
   preorderl(root);cout<<endl;
   cout<<"中序遍历的结果"<<endl;
   inorderl(root);cout<<endl;
   cout<<"后序遍历的结果"<<endl;
   postorderl(root);cout<<endl;
}