建立二叉樹，層序、先序遍歷
 懸賞分：20 - 解決時間：2008-6-30 08:09
用非遞歸算法，c++語言 
1、問題描述 
要求能夠輸入樹的各個結點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲結構的的輸入函數、輸出層序遍歷序列的函數、輸出先序遍歷序列的函數； 
2、要求 
在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、源程序、測試數據和結果、算法的時間復雜度、另外可以提出算法的改進方法。
#include <iostream> 
#include "sq_Queue.h" 
#define M 1000 
using namespace std; 
template<class T> 
struct Btnode 
{T d; 
Btnode *lchild; 
Btnode *rchild; 
}; 
template<class T> 
class Binary_Tree 
{private: 
Btnode<T> *BT; 
public: 
Binary_Tree(){BT=NULL;return;} 
void creat_Binary_Tree(T); 
void pretrav_Binary_Tree(); 
void level( ); 
}； 
template<class T> 
void Binary_Tree<T>::creat_Binary_Tree(T end) 
{ 
Btnode<T> *p; 
T x; 
cin>>x; 
if(x==end) 
return; p=new Btnode<T>; 
p->d=x; 
p->lchild=NULL; 
p->rchild=NULL; 
BT=p; 
creat(p,1,end); 
creat(p,2,end); 
return; 
} 
template<class T> 
static creat(Btnode<T> *p,int k,T end) 
{ 
Btnode<T> *q; 
T x; 
cin>>x; 
if(x!=end) 
{ 
q=new Btnode<T>; 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<class T> 
void Binary_Tree<T>::pretrav_Binary_Tree( ) 
{ 
Btnode<T> *p; 
p=BT; 
pretrav(p); cout<<endl; 
return; 
} 

template<class T> 
static pretrav(Btnode<T> *p) 
{ 
if(p!=NULL) 
{ 
cout<<p->d<<" "; pretrav(p->lchild); pretrav(p->rchild); } 
return 0; 
} 
//————————————按層次遍歷二叉鏈表—————————————— 
template<class T> 
void Binary_Tree<T>::level( ) 
{ 
Btnode<T> *k; 
sq_Queue<Btnode<T>*>q(M); 
if(BT!=NULL) 
q.ins_sq_Queue(BT); 
while(q.flag_sq_Queue( )) 
{ 
k=q.del_sq_Queue( ); 
cout<<k->d<<endl; 
if(k->lchild!=NULL) q.ins_sq_Queue(k->lchild); 
if(k->rchild!=NULL) q.ins_sq_Queue(k->rchild); 
} 
return; 
} 
int main( ) 
{ 
Binary_Tree<int>b; cout<<"輸入各結點值(-1為結束符值):"<<endl; 
b.creat_Binary_Tree(-1); cout<<"前序序列:"<<endl; 
b.pretrav_Binary_Tree( ); 
cout<<"按層次輸出二叉鏈表中所有結點值:"<<endl; 
b.level( ); 
再建立一個用戶自定義文件sq_Queue,把下面的考進去 
#include <iostream> 
using namespace std; 
//定義循環隊列類 
template<class T> //模板聲明，數據元素虛擬類型為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<class T> 
sq_Queue<T>::sq_Queue(int m) 
{mm=m; //存儲空間容量 
q=new T[mm]; //動態申請存儲空間 
front=mm; 
rear=mm; 
s=0; 
return; 
} 
//輸出排頭與隊尾指針以及隊中元素 
template<class T> 
void sq_Queue<T>::prt_sq_Queue() 
{int i; 
cout<<"front="<<front<<endl; 
cout<<"rear="<<rear<<endl; 
if(s==0){cout<<"隊列空！"<<endl; 
return; 
} 
i=front; 
do{i=i+1; 
if(i==mm+1)i=1; 
cout<<q[i-1]<<endl; 
}while(i!=rear); 
return; 
} 
//檢測循環隊列的狀態 
template<class T> 
int sq_Queue<T>::flag_sq_Queue() 
{if((s==1)&&(rear==front))return(-1); //存儲空間已滿，返回-1 
if(s==0)return(0); //循環隊列為空，返回0 
return(1); //正常返回1 
} 
//入隊 
template<class T> 
void sq_Queue<T>::ins_sq_Queue(T x) 
{if((s==1)&&(rear==front)) //存儲空間已滿，上溢錯誤 
{cout<<"Queue_overflow!"<<endl; 
return; 
} 
rear=rear+1; //隊尾指針進一 
if(rear==mm+1)rear=1; 
q[rear-1]=x; //新元素入隊 
s=1; //入隊后隊列非空 
return; 
} 
//退隊 
template<class T> 
T sq_Queue<T>::del_sq_Queue() 
{T y; 
if(s==0) //隊列為空，下溢錯誤 
{cout<<"Queue_underflow!"<<endl; 
return(0); 
} 
front=front+1; //排頭指針進一 
if(front==mm+1)front=1; 
y=q[front-1]; //將退隊元素賦值給變量 
if(front==rear)s=0; 
return(y); //返回退隊元素 
}