二叉樹的遍歷課程設(shè)計(jì)報(bào)告C++含源代碼

-.z.南京理工大學(xué)課程設(shè)計(jì)報(bào)告作者:相蒙蒙學(xué)號(hào)：1教學(xué)點(diǎn):市職業(yè)大學(xué)專業(yè):機(jī)電一體化題目:二叉樹的遍歷指導(dǎo)者：尚鮮蓮評(píng)閱者：2014年4月-.z.**理工大學(xué)課程設(shè)計(jì)報(bào)告評(píng)語綜合成績(jī)：指導(dǎo)者評(píng)語：指導(dǎo)者(簽字)：年月日-.z.課程設(shè)計(jì)報(bào)告摘要摘要：本文主要說明如何實(shí)現(xiàn)二叉樹的遍歷。此次二叉樹的遍歷基于二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)。遍歷方式包括：前序遍歷，中序遍歷，后續(xù)遍歷，層序遍歷。其中前序遍歷和后續(xù)遍歷采用非遞歸算法實(shí)現(xiàn)。編程環(huán)境為VC++，除了遍歷操作外，還增加了求二叉樹的深度，總結(jié)點(diǎn)數(shù)，每層結(jié)點(diǎn)數(shù)，以及最近共同祖先（LCA）問題的算法。關(guān)鍵詞：二叉樹遍歷二叉樹遍歷目錄1問題描述 51.1問題描述：創(chuàng)建二叉樹并遍歷 52、需求分析 53、概要設(shè)計(jì) 53.1．創(chuàng)建二叉樹 53.2二叉樹的非遞歸前序遍歷示意圖 53.3二叉樹的后序非遞歸遍歷示意圖 64、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 64.1二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義 64.2二叉樹數(shù)據(jù)類型定義 75、算法設(shè)計(jì) 85.1創(chuàng)建二叉樹 85.2非遞歸前序遍歷 85.3非遞歸后序遍歷 95.4求二叉樹的高度 105.5求二叉樹每一層的結(jié)點(diǎn)數(shù) 105.6求兩節(jié)點(diǎn)最近共同祖先 115.7算法流程圖 126、程序測(cè)試與調(diào)試126.1函數(shù)之間的調(diào)用關(guān)系 126.2主程序 136.3測(cè)試數(shù)據(jù) 146.4測(cè)試結(jié)果 147、調(diào)試分析 178、遇到的問題及解決辦法 179、心得體會(huì) 1710、參考文獻(xiàn) 181、問題描述1.1問題描述：創(chuàng)建二叉樹并遍歷基本要求：分別運(yùn)用非遞歸的方式完成對(duì)二叉樹的先序和后序遍歷輸出二叉樹的高度輸出每一層的結(jié)點(diǎn)數(shù)查找結(jié)點(diǎn)P和結(jié)點(diǎn)Q的最近共同祖先需求分析1、本程序的功能包括二叉樹的建立，二叉樹的遞歸遍歷，二叉樹的非遞歸遍歷，查詢二叉樹的深度，查詢每層的結(jié)點(diǎn)數(shù)，查找兩個(gè)結(jié)點(diǎn)的最近共同祖先，二叉樹的打印。2、程序運(yùn)行后顯現(xiàn)提示信息，等候用戶輸入0—6以進(jìn)入相應(yīng)的操作功能。3、用戶輸入數(shù)據(jù)完畢，程序?qū)⑤敵鲞\(yùn)行結(jié)果。4、測(cè)試數(shù)據(jù)應(yīng)為字符型數(shù)據(jù)。概要設(shè)計(jì)3．1創(chuàng)建二叉樹輸入數(shù)據(jù)不低于15個(gè)，用遞歸方法建立二叉樹。3.2二叉樹的非遞歸前序遍歷示意圖圖3.2二叉樹前序遍歷示意圖3.3二叉樹的后序非遞歸遍歷示意圖圖3.4二叉樹后序遍歷示意圖4、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)4.1二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義為：template<typenameT>struct BiNode{ BiNode<T>*rchild,*lchild;//指向左右孩子的指針 Tdata;//結(jié)點(diǎn)數(shù)據(jù)信息};4.2二叉樹數(shù)據(jù)類型定義為：template<typenameT>classBiTree{template<typenameT>friendostream&operator<<(ostream&os,BiTree<T>&bt);public: BiTree();//無參構(gòu)造函數(shù) BiTree(intm){};//有參空構(gòu)造函數(shù) BiTree(Tary[],intnum,Tnone);//有參構(gòu)造函數(shù) ~BiTree();//析構(gòu)函數(shù)voidpreorder();//遞歸前序遍歷voidinorder();//遞歸中序遍歷voidpostorder();//遞歸后續(xù)遍歷voidlevelorder();//層序遍歷intcount();//計(jì)算二叉樹的結(jié)點(diǎn)數(shù)intdepth();//計(jì)算二叉樹的深度voiddisplay(ostream&os);//打印二叉樹，有層次voidLevelNum();//計(jì)算每一層結(jié)點(diǎn)數(shù)voidPreOrder();//非遞歸前序遍歷voidPostOrder();//非遞歸后序遍歷voidcreat();//創(chuàng)建二叉樹 TleastmanAncestor(Tva,Tvb);//求樹中任意兩結(jié)點(diǎn)最近共同祖先protected://以下函數(shù)供上面函數(shù)調(diào)用//對(duì)應(yīng)相同功能voidcreat(BiNode<T>*&root);//創(chuàng)建voidrelease(BiNode<T>*&root);//刪除 BiNode<T>*Build(Tary[],intnum,Tnone,intid*);//用數(shù)組創(chuàng)建二叉樹voidPreOrder(BiNode<T>*root);//前序遍歷voidPostOrder(BiNode<T>*root);//后續(xù)遍歷voidLevelNum(BiNode<T>*root);//層序遍歷voidpreorder(BiNode<T>*root);//遞歸前序遍歷voidinorder(BiNode<T>*root);//遞歸中序遍歷voidpostorder(BiNode<T>*root);//遞歸后續(xù)遍歷voidlevelorder(BiNode<T>*root);//層序遍歷intcount(BiNode<T>*root);//計(jì)算結(jié)點(diǎn)數(shù)intdepth(BiNode<T>*root);//計(jì)算深度voiddisplay(ostream&os,BiNode<T>*root,intdep);//打印staticboolleastmanAncestor(BiNode<T>*root,Tva,Tvb,BiNode<T>*&result,BiNode<T>*parrent);//求最近共同祖先private: BiNode<T>*rootptr;};5、算法設(shè)計(jì)5.1創(chuàng)建二叉樹//實(shí)現(xiàn)外部遞歸調(diào)用voidBiTree<T>::creat(){ creat(rootptr);}//類體遞歸創(chuàng)建二叉樹template<typenameT>voidBiTree<T>::creat(BiNode<T>*&root){ Titem; cin>>item;if(item=='*')root=NULL;else { root=newBiNode<T>; root->data=item; creat(root->lchild); creat(root->rchild); }}5.2非遞歸前序遍歷template<typenameT>voidBiTree<T>::PreOrder(){ PreOrder(rootptr);}template<typenameT>voidBiTree<T>::PreOrder(BiNode<T>*root){ stack<BiNode<T>*>s;while(root!=NULL||!s.empty()) {while(root) { cout<<root->data; s.push(root); root=root->lchild; }if(!s.empty()) { root=s.top(); s.pop(); root=root->rchild; } }}5.3非遞歸后序遍歷template<typenameT>voidBiTree<T>::PostOrder(){ PostOrder(rootptr);}template<typenameT>voidBiTree<T>::PostOrder(BiNode<T>*root){stack<BiNode<T>*>s;//定義棧，節(jié)點(diǎn)類型為TreeNodeBiNode<T>*p=root;BiNode<T>*pre=NULL;//pre表示最近一次訪問的結(jié)點(diǎn)while(p||!s.empty()){//沿著左孩子方向走到最左下。while(p){s.push(p);p=p->lchild;}//getthetopelementofthestackp=s.top();//如果p沒有右孩子或者其右孩子剛剛被訪問過if(p->rchild==NULL||p->rchild==pre){//visitthiselementandthenpopitcout<<p->data;s.pop();pre=p;p=NULL;}else{p=p->rchild;}}//endofwhile(p||st.size()!=0)}5.4求二叉樹的高度template<typenameT>intBiTree<T>::depth(){returndepth(rootptr);}template<typenameT>intBiTree<T>::depth(BiNode<T>*root){intrdep,ldep;if(root==NULL)return0;else { ldep=depth(root->lchild); rdep=depth(root->rchild);return(rdep>ldep"rdep:ldep)+1; }}5.5 求二叉樹每一層的結(jié)點(diǎn)數(shù)template<typenameT>voidBiTree<T>::LevelNum(){ LevelNum(rootptr);}template<typenameT>voidBiTree<T>::LevelNum(BiNode<T>*root){ queue<BiNode<T>*>q;intfront,rear,first,last,level; front=rear=first=0; last=level=1;if(root) { q.push(root); rear++;while(front<rear) { root=q.front(); q.pop(); front++;if(root->lchild) { q.push(root->lchild); rear++; }if(root->rchild) { q.push(root->rchild); rear++; }if(front==last) { cout<<"第"<<level<<"層有"<<last-first<<"個(gè)結(jié)點(diǎn)"<<endl; level++; last=rear; first=front; } } }}5.6求兩節(jié)點(diǎn)最近共同祖先template<typenameT>TBiTree<T>::leastmanAncestor(Tn1,Tn2){returnleastmanAncestor(rootptr,n1,n2);}template<typenameT>TBiTree<T>::leastmanAncestor(BiNode<T>*root,Tn1,Tn2){if(root==NULL||root->data==n1||root->data==n2)return-1;if((root->rchild!=NULL)&& (root->rchild->data==n1||root->rchild->data==n2))returnroot->data;if((root->lchild!=NULL)&& (root->lchild->data==n1||root->lchild->data==n2))returnroot->data;if(root->data>n1&&root->data<n2)returnroot->data;if(root->data>n1&&root->data>n2)returnleastmanAncestor(root->lchild,n1,n2);if(root->data<n1&&root->data<n2)returnleastmanAncestor(root->rchild,n1,n2);}5.7算法流程圖程序初始化程序初始化用戶交互用戶交互用戶輸入選擇用戶輸入選擇求共同祖先求每層結(jié)點(diǎn)數(shù)求深度遍歷二叉樹創(chuàng)建二叉樹求共同祖先求每層結(jié)點(diǎn)數(shù)求深度遍歷二叉樹創(chuàng)建二叉樹結(jié)束處理并輸出結(jié)果結(jié)束處理并輸出結(jié)果6、程序測(cè)試與實(shí)現(xiàn)6.1函數(shù)之間的調(diào)用關(guān)系main()main()每層結(jié)點(diǎn)數(shù)求LCA求節(jié)點(diǎn)數(shù)深度遍歷創(chuàng)建每層結(jié)點(diǎn)數(shù)求LCA求節(jié)點(diǎn)數(shù)深度遍歷創(chuàng)建LCA()Levelnum()CLCA()Levelnum()Creat()Count()Depth()Inorder()PInorder()Postorder()Preorder()6.2主程序voidmain(){ BiTree<char>Tree(1);while(1){ cout<<"\t\t歡迎使用本系統(tǒng)??！"<<endl; cout<<"\t\t****************************************"<<endl; cout<<"\t\t**"<<endl; cout<<"\t\t*1--創(chuàng)建一顆二叉樹并顯示*"<<endl; cout<<"\t\t*2--遍歷二叉樹*"<<endl; cout<<"\t\t*3--查詢二叉樹的深度和結(jié)點(diǎn)數(shù)*"<<endl; cout<<"\t\t*4--查詢每層結(jié)點(diǎn)數(shù)*"<<endl; cout<<"\t\t*5--查找兩節(jié)點(diǎn)P和Q的最近共同祖先*"<<endl; cout<<"\t\t*6--退出*"<<endl; cout<<"\t\t**"<<endl; cout<<"\t\t****************************************"<<endl; cout<<"請(qǐng)輸入你的選擇：";int*; cin>>*;switch(*){case1:{ cout<<"請(qǐng)輸入二叉樹的前序遍歷："<<endl; cout<<"（以*作為分支結(jié)尾，例如：AB**C**）"<<endl; Tree.creat(); cout<<Tree; cout<<endl; }break;case2:{ cout<<endl; cout<<"前序遍歷為："; Tree.PreOrder(); cout<<endl; cout<<"中序遍歷為："; Tree.inorder(); cout<<endl; cout<<"后序遍歷為："; Tree.PostOrder(); cout<<endl; cout<<"層序遍歷為："; Tree.levelorder(); cout<<endl; cout<<endl; }break;case3:{ cout<<"樹的深度為："<<Tree.depth()<<endl; cout<<"樹的結(jié)點(diǎn)數(shù)："<<Tree.count()<<endl; cout<<endl; }break;case4:{ Tree.LevelNum(); }break;case5:{charch1,ch2; cout<<"請(qǐng)輸入P數(shù)據(jù)信息："; cin>>ch1; cout<<"請(qǐng)輸入Q數(shù)據(jù)信息："; cin>>ch2; cout<<ch1<<"和"<<ch2<<"的最近共同祖先是"<<Tree.leastm