2012《數(shù)據(jù)結(jié)構(gòu)》上機實驗報告二叉樹遍歷.doc

西華數(shù)學與計算機學院上機實踐報告課程名稱：數(shù)據(jù)結(jié)構(gòu)年級： 2011上機實踐成績：指導(dǎo)教師：唐劍梅姓名：蔣俊上機實踐名稱： 學號：312011080611118上機實踐日期：2012-11-20上機實踐編號：2上機實踐時間：8:00-9:30一、實驗?zāi)康?. 熟練掌握二叉樹在二叉鏈表存儲結(jié)構(gòu)中的常用遍歷方法：先序遞歸遍歷、中序遞歸和非遞歸遍歷、后序遞歸遍歷。了解二叉樹的按層遍歷、先序非遞歸遍歷及后序非遞歸遍歷。2. 用樹解決實際問題，如哈夫曼編碼等。加深對“數(shù)據(jù)結(jié)構(gòu)+算法=程序”的理解和認識，提高編寫較復(fù)雜程序的能力。二、實驗內(nèi)容 建立一棵二叉樹，分別用“先根非遞歸”方法、“按層遍歷”的方法遍歷。三、實驗環(huán)境 硬件: 微型計算機P4軟件: Windows XP+Microsoft Visual C+6.04、 程序源碼及調(diào)試過程#include #include 2.h#include 3.htypedef int ElemType;struct NodeType /定義結(jié)點 結(jié)構(gòu)體 ElemType data; NodeType *lch,*rch;class BiTree /定義 二叉樹類 public: BiTree()root=NULL; /構(gòu)造函數(shù) BiTree()destroy(root) ; /析構(gòu)函數(shù) void inorder() /中序遍歷 inorder(root); void preordertswap() /利用先序遍歷方法交換左右子樹 preorderswap(root); int theight() /求二叉樹高度 return height(root); void creat0(); void preoder(); /先根遍歷非遞歸 void levelorder(); /按層遍歷二叉樹 private: NodeType *root; /數(shù)據(jù)成員，樹根 NodeType *creat(); /建立二叉樹遞歸方法 void inorder(NodeType *p); /中序遍歷 void preorderswap(NodeType *p); /利用先序遍歷方法交換左右子樹 int height(NodeType *p); /求二叉樹高度遞歸算法 void destroy(NodeType* &p); /刪除二叉樹所有結(jié)點 ;void BiTree:creat0() /建立樹函數(shù)， cout請按照樹的先序遍歷順序組織數(shù)據(jù)endl; cout若結(jié)點信息是int，把每個結(jié)點的空孩子以0輸入;endl; cout例如一個結(jié)點的二叉樹11，輸入：11 0 0;endl; root=creat(); /調(diào)用私有creat(); NodeType * BiTree:creat() /遞歸建立二叉樹算法 NodeType *p; ElemType x; coutx; if( x=0) p=NULL; else p=new NodeType; p-data=x;p-lch=creat(); /遞歸調(diào)用自身p-rch=creat(); return p; void BiTree:preoder() /先根遍歷非遞歸NodeType *q;SqStack s;q=root;int boo=1;cout先根非遞歸遍歷endl;dowhile(q!=NULL)coutdata;s.push(q);q=q-lch;if(s.IsEmpty()boo=0;elseq=s.pop();q=q-rch;while(boo);coutlch); coutdatarch);void BiTree:preorderswap(NodeType *p) /利用先序遍歷方法交換左右子樹 if(p != NULL) NodeType *r; r=p-lch; p-lch=p-rch; p-rch=r;/上面幾條語句可以認為對結(jié)點的訪問（交換左右孩子）/替換了原來的： coutdatalch); preorderswap(p-rch);void BiTree:destroy(NodeType* &p) /刪除二叉樹所有結(jié)點if(p != NULL) destroy(p-lch);destroy(p-rch);delete p;p = NULL;int BiTree:height(NodeType *p) /求二叉樹高度(遞歸) if(p = NULL) return 0; else int hl=height(p-lch); int hr=height(p-rch); return 1 + (hlhr?hl:hr); /1加上hl和hr的較大值 void BiTree:levelorder() /按層遍歷SqQueueq;NodeType *p;p=root;if(p!=NULL) q.EnQueue(p);while(!q.IsEmpty()p=q.DeQueue();coutdatalch!=NULL) q.EnQueue(p-lch);if(p-rch!=NULL) q.EnQueue(p-rch);/-int main() int k; BiTree root0; /聲明創(chuàng)建二叉樹對象，調(diào)用構(gòu)造函數(shù) do coutnn; coutnn 1. 建立二叉樹; coutnn 2. 交換左右子樹; coutnn 3. 求二叉樹深度; coutnn 4.先根非遞歸遍歷; coutnn 5.按層遍歷二叉樹; coutnn 6. 結(jié)束程序運行; coutn=; coutk; switch(k) case 1: coutn 建立二叉樹：; root0.creat0(); coutn 中根遍歷結(jié)果：; root0.inorder(); break; case 2: root0.preordertswap(); coutn 交換左右子樹后中根遍歷結(jié)果：; root0.inorder(); break; case 3: int deep; deep=root0.theight(); coutn 樹的深度是：deep; break; case 4: coutn 先根遍歷的結(jié)果：; root0.preoder(); break; case 5: coutn 按層遍歷二叉樹的結(jié)果 ：; root0.levelorder(); break; case 6: break; cout=1 & k6);return 0;/棧的順序存儲結(jié)構(gòu)，順序棧類#include#include /-棧的順序存儲結(jié)構(gòu)-/typedef int ElemType; / 數(shù)據(jù)元素的類型/const int MAXSIZE=100; / 數(shù)組的容量template class SqStack private: T *elem; int maxSize; int top; public: SqStack(int s=30); SqStack()deleteelem; void push(T item); T pop(); void PrintOut(); int IsEmpty()return top=-1; int IsFull()return top=maxSize-1;/-templateSqStack:SqStack(int s)top=-1;maxSize=s;elem=new TmaxSize;for(int i=0;imaxSize;i+)elemi=0; templatevoid SqStack:push(T item) if(!IsFull()top+;elemtop=item;templateT SqStack:pop() T x;if(!IsEmpty() x=elemtop;top-;return x;templatevoid SqStack:PrintOut() int t; if(!IsEmpty()cout棧已空endl;elsei=top;while(i!=-1)coutdata=elemi;i-;隊列的順序存儲結(jié)構(gòu)#includetemplateclass SqQueuepublic:SqQueue(int sz=30); SqQueue()deleteelem; void EnQueue(T item); T DeQueue(); T GetFront(); int IsEmpty()return front=rear; int IsFull()return (rear+1)%maxSize=front; int Length()return (rear-front+maxSize)%maxSize; void PrintOut();private:int front,rear;T*elem;int maxSize;templateSqQueue:SqQueue(int sz)front=rear=0;maxSize=sz;elem=new TmaxSize;for(int i=0;imaxSize;i+)elemi=0;templatevoid SqQueue:EnQueue(T item)if(!IsFull()rear=(rear+1)%maxSize;elemrear=item;templateT SqQueue:DeQueue()if(!IsEmpty()front=(front+1)%maxSize;return elemfront;templateT SqQueue:GetFront()if(!IsEmpty()return elem(front+1)%maxSize;templatevoid Sq