二叉树的遍历 先序 中序 后序 遍历和层次遍历

				建立二叉树，层序、先序遍历
				 悬赏分：20 - 解决时间：2008-6-30 08:09
				用非递归算法，c++语言 
				1、问题描述 
				要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数； 
				2、要求 
				在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。
				#include  
				#include "sq_Queue.h" 
				#define M 1000 
				using namespace std; 
				template 
				struct Btnode 
				{T d; 
				Btnode *lchild; 
				Btnode *rchild; 
				}; 
				template 
				class Binary_Tree 
				{private: 
				Btnode *BT; 
				public: 
				Binary_Tree(){BT=NULL;return;} 
				void creat_Binary_Tree(T); 
				void pretrav_Binary_Tree(); 
				void level( ); 
				}； 
				template 
				void Binary_Tree::creat_Binary_Tree(T end) 
				{ 
				Btnode *p; 
				T x; 
				cin>>x; 
				if(x==end) 
				return; p=new Btnode; 
				p->d=x; 
				p->lchild=NULL; 
				p->rchild=NULL; 
				BT=p; 
				creat(p,1,end); 
				creat(p,2,end); 
				return; 
				} 
				template 
				static creat(Btnode *p,int k,T end) 
				{ 
				Btnode *q; 
				T x; 
				cin>>x; 
				if(x!=end) 
				{ 
				q=new Btnode; q->d=x; 
				q->lchild=NULL; 
				q->rchild=NULL; 
				if(k==1) p->lchild=q; if(k==2) p->rchild=q; creat(q,1,end); creat(q,2,end); } 
				return 0; 
				} 
				//————————————前序遍历二叉链表—————————————— 
				template 
				void Binary_Tree::pretrav_Binary_Tree( ) 
				{ 
				Btnode *p; 
				p=BT; 
				pretrav(p); cout				return; 
				} 
				
				template 
				static pretrav(Btnode *p) 
				{ 
				if(p!=NULL) 
				{ 
				cout				return 0; 
				} 
				//————————————按层次遍历二叉链表—————————————— 
				template 
				void Binary_Tree::level( ) 
				{ 
				Btnode *k; 
				sq_Queueq(M); 
				if(BT!=NULL) 
				q.ins_sq_Queue(BT); 
				while(q.flag_sq_Queue( )) 
				{ 
				k=q.del_sq_Queue( ); 
				cout				if(k->lchild!=NULL) q.ins_sq_Queue(k->lchild); 
				if(k->rchild!=NULL) q.ins_sq_Queue(k->rchild); 
				} 
				return; 
				} 
				int main( ) 
				{ 
				Binary_Treeb; cout				b.creat_Binary_Tree(-1); cout				b.pretrav_Binary_Tree( ); 
				cout				b.level( ); 
				再建立一个用户自定义文件sq_Queue,把下面的考进去 
				#include  
				using namespace std; 
				//定义循环队列类 
				template //模板声明，数据元素虚拟类型为T 
				class sq_Queue 
				{private: //数据成员 
				int mm; //存储空间容量 
				int front; //排头指针 
				int rear; //队尾指针 
				int s; //标志 
				T *q; //循环队列存储空间首地址 
				public: //成员函数 
				sq_Queue(int); //构造函数，建立空循环队列 
				void prt_sq_Queue(); //输出排头与队尾指针以及队中元素 
				int flag_sq_Queue(); //检测循环队列的状态 
				void ins_sq_Queue(T); //入队 
				T del_sq_Queue(); //退队 
				}; 
				//建立容量为mm的空循环队列 
				template 
				sq_Queue::sq_Queue(int m) 
				{mm=m; //存储空间容量 
				q=new T[mm]; //动态申请存储空间 
				front=mm; 
				rear=mm; 
				s=0; 
				return; 
				} 
				//输出排头与队尾指针以及队中元素 
				template 
				void sq_Queue::prt_sq_Queue() 
				{int i; 
				cout				cout				if(s==0){cout				return; 
				} 
				i=front; 
				do{i=i+1; 
				if(i==mm+1)i=1; 
				cout				}while(i!=rear); 
				return; 
				} 
				//检测循环队列的状态 
				template 
				int sq_Queue::flag_sq_Queue() 
				{if((s==1)&&(rear==front))return(-1); //存储空间已满，返回-1 
				if(s==0)return(0); //循环队列为空，返回0 
				return(1); //正常返回1 
				} 
				//入队 
				template 
				void sq_Queue::ins_sq_Queue(T x) 
				{if((s==1)&&(rear==front)) //存储空间已满，上溢错误 
				{cout				return; 
				} 
				rear=rear+1; //队尾指针进一 
				if(rear==mm+1)rear=1; 
				q[rear-1]=x; //新元素入队 
				s=1; //入队后队列非空 
				return; 
				} 
				//退队 
				template 
				T sq_Queue::del_sq_Queue() 
				{T y; 
				if(s==0) //队列为空，下溢错误 
				{cout				return(0); 
				} 
				front=front+1; //排头指针进一 
				if(front==mm+1)front=1; 
				y=q[front-1]; //将退队元素赋值给变量 
				if(front==rear)s=0; 
				return(y); //返回退队元素 
				}