erchashu.rar_二叉树的遍历

建立二叉树，层序、先序遍历 悬赏分：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); //返回退队元素 }