tree.cpp

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

//二叉树的三种遍历
#include<iostream>
using namespace std;
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 preorder( bitree *root)
{  bitree *p;
 p=root;
if(p!=NULL)
{ cout<<p->data;
   preorder(p->lchild);
   preorder(p->rchild);
}
}
void preorder1(bitree *root)
{ bitree *p,*s[100];
  int top=0;
  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 inorder( bitree *root)
{  bitree *p;
p=root;
if(p!=NULL)
{ 
   inorder(p->lchild);
   cout<<p->data<<" ";
   inorder(p->rchild);
}
}
void inorder1( 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 postorder( bitree *root)
{  bitree *p;
p=root;
if(p!=NULL)
{ 
   postorder(p->lchild);
   postorder(p->rchild);
cout<<p->data<<" ";
}
}
void postorder1( 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;
  preorder(root);cout<<endl;
  preorder1(root);cout<<endl;
  cout<<"中序遍历的结果"<<endl;
  inorder(root);cout<<endl;
  inorder1(root);cout<<endl;
  cout<<"后序遍历的结果"<<endl;
  postorder(root);cout<<endl;
  postorder1(root);cout<<endl;
}