數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)二叉樹遍歷C++語言

1、淮陰工學(xué)院實(shí)踐報(bào)告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目：二叉樹遍歷系別：計(jì)算機(jī)工程學(xué)院專業(yè)：軟件工程班級(jí)：軟件1111學(xué)生姓名：周淼學(xué)號(hào)：1111315217起止日期：2012年12月24日2012年12月30日指導(dǎo)教師：寇海洲摘要：現(xiàn)代社會(huì)生活中，計(jì)算機(jī)扮演著重要角色，而隨著計(jì)算機(jī)運(yùn)行速度的不斷加快，對(duì)數(shù)據(jù)的處理能力也日益增強(qiáng)，因此，程序所涉及的數(shù)據(jù)成爆發(fā)式增長。隨之而來的問題就是如何科學(xué)有效的對(duì)數(shù)據(jù)進(jìn)行操作，使得計(jì)算機(jī)的時(shí)間和空間利用率最高。針對(duì)這樣的問題，我選擇了二叉樹對(duì)數(shù)據(jù)的各種操作作為我的課程設(shè)計(jì)主題，希望通過課程設(shè)計(jì)來提高對(duì)數(shù)據(jù)的處理能力，促進(jìn)對(duì)數(shù)據(jù)結(jié)構(gòu)課程的理解，在日后面向?qū)ο蟮某绦蛟O(shè)計(jì)中科

2、學(xué)的規(guī)劃數(shù)據(jù)結(jié)構(gòu)。在本次課程設(shè)計(jì)中，二叉樹的建立使用了遞歸算法，遍歷則同時(shí)使用了遞歸與非遞歸的算法，同時(shí)，在遍歷算法的實(shí)現(xiàn)中使用了棧結(jié)構(gòu)與隊(duì)列結(jié)構(gòu)，這大大方便了二叉樹的遍歷。在前序中序后續(xù)遍歷算法中，分別實(shí)現(xiàn)了遞歸與非遞歸算法，從實(shí)際應(yīng)用中體驗(yàn)了遞歸這一算法的優(yōu)越性。關(guān)鍵詞：二叉樹建立，遞歸與非遞歸，遍歷，棧，隊(duì)列編號(hào)：47淮陰工學(xué)院軟件工程專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)答辯記錄課題名稱：二叉樹的算法班級(jí)軟件吐11學(xué)號(hào)1111315217姓名周淼答辯記錄問題1:課題中涉及到哪些數(shù)據(jù)結(jié)構(gòu)和算法？答：1）數(shù)組，二叉樹，棧，隊(duì)列，線性表2）二叉樹的中序.前序.后序的遞歸,非遞歸遍歷算法，層次序遍歷非遞歸算法，

3、棧,隊(duì)列的實(shí)現(xiàn)算法問題2：課題研究和設(shè)計(jì)中的關(guān)鍵技術(shù)是什么？答：關(guān)鍵技術(shù)是二叉樹的建立，以及棧結(jié)構(gòu).隊(duì)列的算法實(shí)現(xiàn)問題3：課題的主要功能和模塊有哪些？答：1）主要功能：根據(jù)數(shù)據(jù)建立二叉樹，實(shí)現(xiàn)二叉樹的中序.前序.后序遍歷2）模塊：棧的應(yīng)用，隊(duì)列結(jié)構(gòu)的應(yīng)用，二叉樹的操作問題4：課題在實(shí)現(xiàn)過程中遇到的主要難點(diǎn)有哪些？答：遍歷二叉樹過程中棧結(jié)構(gòu)以及隊(duì)列的使用問題5：課題中未能實(shí)現(xiàn)的功能有哪些？答：以樹形結(jié)構(gòu)輸出完全二叉樹記錄人：寇海洲2012年12月28H4調(diào)試與操作說明211.1 二叉樹與樹結(jié)構(gòu)61.2 面向?qū)ο蟮某绦蛟O(shè)計(jì)61.3 二叉樹遍歷的應(yīng)用61.4 軟件運(yùn)行環(huán)境：VisualC+6.0版本

4、62概要設(shè)計(jì)71 .1總體功能結(jié)構(gòu)72 .2數(shù)據(jù)結(jié)構(gòu)部分設(shè)計(jì)72.2.1結(jié)點(diǎn)結(jié)構(gòu)72.2.2二叉樹結(jié)構(gòu)83詳細(xì)設(shè)計(jì)133.1 建立二叉樹133.1.1 功能描述133.1.2 算法原理133.1.3 具體耕133.2前序遍歷143.2.1功能原理143.2.2算法原理143.2.3具體程序1433中序遍歷153.3.1功能原理153.3.2算法原理153.3.3具體葩153.4后序遍歷163.4.1功能原理163.4.2算法原理163.4.3具體衙173.5層次序非遞歸遍歷183.5.1功能原理183.5.2算法原理183.5.3具體程序183.6棧結(jié)構(gòu)193.6.1功能原理193.6.2算法

5、原理193.6.3具體靳193.7隊(duì)列結(jié)構(gòu)203.7.1功能原理203.7.2算法原理203.7.3具體葩20致謝24參考文獻(xiàn)25附錄:261需求分析1.1二叉樹與樹結(jié)構(gòu)樹結(jié)構(gòu)的是建立在數(shù)據(jù)邏輯結(jié)構(gòu)基礎(chǔ)上的數(shù)據(jù)結(jié)構(gòu)類型，二義樹則是樹結(jié)構(gòu)中最常見和使用最多的類型。通過對(duì)二叉樹的操作，可以實(shí)現(xiàn)多種數(shù)據(jù)操作，如排序、查找等。一個(gè)好的二叉樹遍歷算法應(yīng)包含以下功能：1）以遞歸和非遞歸方法建立二義樹或完全二義樹：2）實(shí)現(xiàn)二義樹的前序遍歷、中序遍歷、后序遍歷；3）每種遍歷算法皆以遞歸和非遞歸方法實(shí)現(xiàn)；4）在具體實(shí)現(xiàn)時(shí)應(yīng)用其他數(shù)據(jù)結(jié)構(gòu)類型對(duì)數(shù)據(jù)進(jìn)行操作，如：棧，隊(duì)列，數(shù)組。1. 2面向?qū)ο蟮某绦蛟O(shè)計(jì)在面向?qū)ο?/p>

6、的程序設(shè)il中，模板的使用很普遍，因此，如何在程序設(shè)訃中使用模板使得方法的實(shí)現(xiàn)與定義分開，程序模塊化，既方便了程序設(shè)計(jì)者，乂為程序的后期維護(hù)帶來便利。1.3 二叉樹遍歷的應(yīng)用當(dāng)數(shù)據(jù)以數(shù)組或文檔形式存儲(chǔ)在內(nèi)存時(shí)，其數(shù)據(jù)之間雖有邏輯聯(lián)系，卻過于分散，因此，建立二義樹以存儲(chǔ)數(shù)據(jù)并且遍歷該二義樹，可以從邏輯上理順數(shù)據(jù)之間的關(guān)系，使得原本分?jǐn)?shù)的數(shù)據(jù)排列的有序且可黑。一個(gè)好的二義樹應(yīng)用算法其空間復(fù)雜度與時(shí)間復(fù)雜度必然最低，這樣給程序帶來時(shí)間和空間上的極大優(yōu)化。1.4 軟件運(yùn)行環(huán)境：VisualC+6.0版本2概要設(shè)計(jì)2.1總體功能結(jié)構(gòu)二叉樹的遍歷，主要包含以下功能：1)建立二義樹：遞歸方法、非遞歸方法2)

7、中序遍歷：遞歸方法、非遞歸方法3)前序遍歷：遞歸方法、非遞歸方法4)后序遍歷：遞歸方法、非遞歸方法5)棧結(jié)構(gòu)使用：遍歷時(shí)輸入臨時(shí)變量以保存6)隊(duì)列結(jié)構(gòu)使用：完全二叉樹遍歷時(shí)用以存儲(chǔ)數(shù)據(jù)2. 2數(shù)據(jù)結(jié)構(gòu)部分設(shè)計(jì)2.2.1結(jié)點(diǎn)結(jié)構(gòu)一叉樹結(jié)點(diǎn)結(jié)構(gòu)中包數(shù)據(jù)域(data),指針域(*leftChild,*rightChild)o結(jié)點(diǎn)結(jié)構(gòu)的代碼如下：structBinTreeNode樹結(jié)點(diǎn)Tdata;BinTreeNode*leftChild;BinTreeNode*rightChild;BinTreeNodeO：leftChild(NULL),rightChild(NULL)BinTreeNode(Tx

8、,BinTreeNode*1=NULL,BinTreeNode*r=NULL):leftChild(l),rightChiId(r)data二x;棧結(jié)構(gòu)結(jié)點(diǎn)包含數(shù)據(jù)域(data),指針域link),實(shí)現(xiàn)代碼如下:structStackNode棧結(jié)點(diǎn)Tdata;StackNode*link;StackNode(Td=0,StackNode*next二NULL):link(next),data(d);隊(duì)列結(jié)構(gòu)結(jié)點(diǎn)包含數(shù)據(jù)域(data),指針域(*link),實(shí)現(xiàn)代碼如下：structLinkXodeTdata;LinkNode*link;LinkNode(LinkNode*ptr二NULL)lin

9、k二ptr;)LinkNode(constT&item,LinkNode*ptr=NULL)data二item;link=ptr;););2.2.2二叉樹結(jié)構(gòu)二叉樹包含了遞歸、非遞歸建樹過程，遞歸、非遞歸的前序遍歷、中序遍歷、后續(xù)遍歷過程。二義樹的類定義包含各種操作，實(shí)現(xiàn)代碼如下：template(typenameTclassBinaryTree二義樹類定義public:BinaryTree():root(NULL)BinaryTree(Tvalue):root(NULL)RefValue二value;BinaryTree(BinaryTree&s)if(this!=&s)root=Copy(

10、s-root);ABinaryTree()destroy(root);BinTreeNodeAParent(BinTreeNode*t)return(root二二NULLroot二二t)?NULL:Parent(root,t);BinTreeNode*LeftChild(BinTreeNode*t)return(t!=NULL)?t-leftChiId:NULL;BinTreeNode*RightChiId(BinTreeNode*t)return(t!=NULL)?t-rightCh訂d:ULL;voidPreOrder(void(*visit)(BinTreeNode*t)PreOrder

11、(root,visit):voidInOrder(void(*visit)(BinTreeNode*t)InOrder(root,visit);voidPostOrder(void(*visit)(BinTreeNode*t)PostOrder(root,visit);voidCreateCompBinTree(T*CBT,intnum)建立完全二義樹CreateCompBinTree(CBT,num,0,root);層次序遍歷voidlevelOrder(void(*visit)(BinTreeNode*t);遍歷遍歷voidInOrder1(void(*visit)(BinTreeNode

12、*t):非遞歸中序voidPostOrderl(void(*visit)(BinTreeNode*t);非遞歸后序遍歷friendistream&operator(istream&in,BinaryTree&Tree)/輸入二義樹TreeCreateBinTree(in,Treeroot);returnin;)棧結(jié)構(gòu)的定義中，包含了對(duì)數(shù)據(jù)的入棧、出棧、清空等基本操作，實(shí)現(xiàn)代碼如下templateclassLinkedStackprivate:StackNode*top;public:LinkedStackO:top(NULL)無頭結(jié)點(diǎn)ALinkedStackOmakeEmpty();)void

13、Push(constT&x):boolPop(T&x);boolIsEmpty()constreturntop二二NULL;)boolIsFull()constreturnfalse;voidmakeEmpty();friendostreamftoperator(ostream&os,LinkedStack&s)os/zStackSize:z/sgetSize()endl;Stackode*p=s.top;inti二0;while(p)os(3+i：p-dataendl;p二p-link;)returnos;)；template(typenameTvoidLinkedStack:makeEmp

14、ty()StackNode*p;while(top)p二top;top=top-link;deletep;)隊(duì)列的類定義，實(shí)現(xiàn)了對(duì)數(shù)據(jù)的入隊(duì)、出隊(duì)操作，實(shí)現(xiàn)代碼如下：template(typenameTclassLinkedQueue無頭結(jié)點(diǎn)public:LinkedQueue()rear二NULL;front二NULL;ALinkedQueue()makeEmpty();)boolEnQueue(constT&x):boolDeQueue(T&x):voidmakeEmpty();boolIsEmpty()constreturnfront二二NULL;)friendostream&opera

15、tor(ostream&os,LinkedQueue&Q)LinkNode*p=Q.front;inti二0;while(p)os+ip-dataendl;p=p-link;)osQueueSize：Q.getSize()endl;returnos;)voidoutput();protected:LinkNode*front,*rear;3. 1建立二叉樹3.1.1 功能描述二義樹是程序的核心，如何合理的建立至關(guān)重要。本實(shí)例中使用遞歸和非遞歸方法分別建立二義樹，二義樹的數(shù)據(jù)來源于程序開始時(shí)建立的數(shù)組。建立后的二叉樹保存，并且留作之后的遍歷使用。3.1.2 算法原理本實(shí)例使用的是完全二叉樹，首先

16、建立頭結(jié)點(diǎn)，并且保存數(shù)據(jù)，然后根據(jù)遞歸方法，分別建立其左右孩子結(jié)點(diǎn)，且左右孩子結(jié)點(diǎn)的指針域指向空。3.1.3 具體程序以遞歸方式建立二叉樹，每次建立一個(gè)結(jié)點(diǎn)后，將其左右孩子指針域置空，成為葉子結(jié)點(diǎn)。具體實(shí)現(xiàn)代碼如下：templatevoidBinaryTree:CreateBinTree(istream&in,BinTreeNodesubTree)Titem;if(initem)i(item!=RefValue)subTree=newBinTreeNode(item):/CreateRootassert(subTree);CreateBinTree(in,subTree-leftChild);

17、/CreateleftchildtreeCreateBinTree(in,subTree-rightChiId);/Createreghtchildtree)else(subTree=NULL;)建立完全二義樹temp1atevoidBinaryTree:CreateCompBinTree(T*CBT,intnum,intrt,BinTreeNodesubTree)if(rt=num)subTree=NULL;)elsesubTree二newBinTreeNode(CBTrtl);)CreateCompBinTree(CBT,num,2*rt+l,subTree-)leftChild);Cre

18、ateCompBinTree(CBT,num,2*rt+2,subTree-rightChild);)3. 2前序遍歷3. 2.1功能原理通過前序遍歷，將二義樹中的數(shù)據(jù)按照前序遍歷的結(jié)果輸出，達(dá)到前序便利的目的，方便數(shù)據(jù)的使用。3. 2.2算法原理前序遍歷使用了遞歸與非遞歸兩種方法，在程序頭文件中定義了兩個(gè)函數(shù)分別實(shí)現(xiàn)其功能。遞歸時(shí)，輸出第一個(gè)結(jié)點(diǎn)數(shù)據(jù)時(shí)，找到數(shù)據(jù)，然后找到其后面的數(shù)據(jù)，然后依次遞歸輸出。非遞歸時(shí)，使用棧和隊(duì)列結(jié)構(gòu)，將部分?jǐn)?shù)據(jù)保存在?；蜿?duì)列中，等待將數(shù)據(jù)放到合適位置。3. 2.3具體程序1)遞歸算法實(shí)現(xiàn)：template(typenameTvoidBinaryTree:PreO

19、rder(BinTreeXode*subTree,void(*visit)(BinTreeNode*t)it(subTree!=NULL)visit(subTree);PreOrder(subTree-leftChild,visit);PreOrder(subTree-rightChild,visit);2)非遞歸算法實(shí)現(xiàn):templatevoidBinaryTree：:PreOrderl(void(*visit)(BinTreeNode*t)LinkedStackBinTreeNode*S;BinTreeNode*p二root:S.Push(NULL);while(p!=NULL)visit

20、(p);訪問結(jié)點(diǎn)if(p-rightChild!=NULL)S.Push(p-rightChild):預(yù)留右指針在棧中i(p-leftChild!=NULL)p=p-leftChild;進(jìn)左子樹elseS.Pop(p):左子樹為空，ill堆棧彈出)3.3中序遍歷3.3.1功能原理通過中序遍歷，將二義樹中的數(shù)據(jù)按照中序序遍歷的結(jié)果輸出，達(dá)到中序遍歷的目的，實(shí)現(xiàn)數(shù)據(jù)的最優(yōu)，方便數(shù)據(jù)的使用。3.3.2算法原理中序遍歷使用了遞歸與非遞歸兩種方法，在程序頭文件中定義了兩個(gè)函數(shù)分別實(shí)現(xiàn)其功能。遞歸時(shí)，輸出第一個(gè)結(jié)點(diǎn)數(shù)據(jù)時(shí)，找到數(shù)據(jù)，然后依次找到其后面的數(shù)據(jù)，然后依次遞歸輸出。非遞歸時(shí)，使用棧和隊(duì)列結(jié)構(gòu)，將

21、部分?jǐn)?shù)據(jù)保存在棧與隊(duì)列中，等待將數(shù)據(jù)放到合適位置。3.3.3具體程序1)遞歸算法實(shí)現(xiàn)：template(typenameTvoidBinaryTree:InOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t)i(subTree!=NULL)InOrder(subTree-leftChild,visit);visit(subTree);InOrder(subTree-rightChiId,visit);)2)非遞歸算法實(shí)現(xiàn)：templatevoidBinaryTree:InOrderl(void(水visit)(BinTreeNode*t)非

22、遞歸中序遍歷LinkedStackBinTreeNode*S;BinTreeNode*p二root;while(p!二NULL!S.IsEmpty()while(p!二NULL)S遍歷指針向左下移動(dòng)-Push(p);該子樹沿途結(jié)點(diǎn)進(jìn)棧p=p-leftChild;)i(!S.IsEmpty()S棧不空時(shí)退棧Pop(P)；visit(p);退棧,訪問p=p-rightChiId;/遍歷指針進(jìn)至ij右子女)3.4后序遍歷1 .4.1功能原理通過后序遍歷，將二義樹中的數(shù)據(jù)按照后序遍歷的結(jié)果輸出，達(dá)到后序遍歷的目的，實(shí)現(xiàn)數(shù)據(jù)的最優(yōu)，方便數(shù)據(jù)的使用。3 .4.2算法原理后序遍歷使用了遞歸與非遞歸兩種方法，

23、在程序頭文件中定義了兩個(gè)函數(shù)分別實(shí)現(xiàn)其功能。遞歸時(shí)，輸出第一個(gè)結(jié)點(diǎn)數(shù)據(jù)時(shí)，找到數(shù)據(jù)，然后依次找到其后面的數(shù)據(jù)，然后依次遞歸輸出。非遞歸時(shí)，使用棧和隊(duì)列結(jié)構(gòu)，將部分?jǐn)?shù)據(jù)保存在棧與隊(duì)列中，等待將數(shù)據(jù)放到合適位置。3.4.3具體程序1)遞歸算法實(shí)現(xiàn)：template(typenameTvoidBinaryTree:PostOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t)il(subTree!=NULL)PostOrder(subTree-leftChild,visit);PostOrder(subTree-rightChild,visit);

24、visit(subTree);)2)非遞歸算法實(shí)現(xiàn)：templatevoidBinaryTree:PostOrder1(void(水visit)(BinTreeNode*t)非遞歸后序遍歷LinkedStackstkNodeS;stkNodew;BinTreeNode*p=root;/p是遍歷指針dowhile(p!=NULL)w.ptr=p;w.tag=stkNode:L;枚舉類型定義在structstkNode中，如定義為全局性就簡(jiǎn)單了S.Push(w);p=p-leftChild;)intcontinuel=1;while(continuel&!SIsEmpty()SPop(w);p=w

25、.ptr;switch(w.tag)判斷棧頂?shù)膖ag標(biāo)記casestkNode:L:w-tag=stkNode:R;SPush(w);continuel=0;p二p-rightChild;break;casestkNode:R:visit(p):break;while(!S.IsEmptyO);繼續(xù)遍歷其他結(jié)點(diǎn)coutendl:)3.5層次序非遞歸遍歷3.5.1功能原理層次序非遞歸遍歷，依據(jù)的是遞歸原理，每次遍歷一個(gè)結(jié)點(diǎn)后，同時(shí)讓其左右孩子入隊(duì)，以便達(dá)到層次序的目的。3.5.2算法原理每次遍歷完一個(gè)結(jié)點(diǎn)后，檢查該結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)，如果是葉子結(jié)點(diǎn)則繼續(xù)下一結(jié)點(diǎn)的遍歷，否則其左右孩子入隊(duì)，繼續(xù)遍

26、歷。3.5.3具體程序template(typenameTvoidBinaryTree：levelOrder(void(*visit)(BinTreeNode*t)層次序遍歷if(root二二NULL)return;LinkedQueueBinTreeNode*Q;BinTreeNode*p=root;visit(p);Q.EnQueue(p);while(!Q.IsEmpty()Q.DeQueue(p);i(p-leftChild!=NULL)visit(p-leftChild);Q.EnQueue(p-leftChild);)i(p-rightchild!=NULL)visit(p-rig

27、htChild);Q.EnQueue(p-rightChiId);3. 6棧結(jié)構(gòu)3. 6.1功能原理運(yùn)用棧結(jié)構(gòu)，在非遞歸算法中，未輸出的數(shù)據(jù)暫時(shí)存入棧中，依據(jù)先進(jìn)后出原貝IJ,方便了二叉樹的遍歷。4. 6.2算法原理二叉樹的結(jié)點(diǎn)信息，保存在棧中。第一個(gè)入棧的數(shù)據(jù)元素保存在棧底，后進(jìn)棧的在上方，現(xiàn)出棧。5. 6.3具體程序templatevoidLinkedStack:Push(constT&x)top二newStackNode(x,top):)templateboolLinkedStack:Pop(T&x)if(IsEmptyO)returnfalse;)StackNode*p=top;top

28、二top-1ink;x=p-data;deletep;returntrue;6. 7隊(duì)列結(jié)構(gòu)3. 7.1功能原理運(yùn)用隊(duì)列結(jié)構(gòu)，在層次序遍歷算法中，未輸出的數(shù)據(jù)暫時(shí)存入隊(duì)列中，依據(jù)先進(jìn)先出原則，方便了二叉樹的遍歷。4. 7.2算法原理層次序遍歷二義樹信息時(shí)，二義樹的結(jié)點(diǎn)信息保存在隊(duì)列中。第一個(gè)入隊(duì)的數(shù)據(jù)元素保存隊(duì)首，后入隊(duì)的元素依次連接上，先入隊(duì)的先出隊(duì)。5. 7.3具體程序template(typenameTvoidLinkedQueue:makeEmptyOLinkNode*p;while(front)p=front;front二front-link;deletep;template(typ

29、enameTboolLinkedQueue:EnQueue(constT&x)if(!front)front=rear二newLinkNode(x);if(!front)returnfalse;elserear-link=newLinkNode(x);if(!(rear-link)returnfalse;rear=rear-link;)returntrue;)template(typenameTboolLinkedQueue:DeQueue(T&x)if(IsEmptyO)returnfalse;LinkNode*p二front;x=front-)data;front二front-1ink;d

30、eletep;returntrue;template(typenameTvoidLinkedQueue:：output()LinkNode*p二front;inti=1;while(idatauendl;p二plink;i+;)4調(diào)試與操作說明操作說明：當(dāng)程序運(yùn)行后，會(huì)在控制臺(tái)提示一下文字：”從數(shù)組數(shù)據(jù)建立完全二義樹：”，“輸入二叉樹的元素總個(gè)數(shù)：”，然后從鍵盤輸入二叉樹元素個(gè)數(shù)，緊接著系統(tǒng)會(huì)自動(dòng)運(yùn)行，得到各種遍歷結(jié)果。運(yùn)行截圖：完全二義樹32個(gè)元素時(shí)的運(yùn)行截圖?C:UsersVRADesktopiAAiHABinaryTreeDebugBinarrTree.exenMC:UsersVRADe

31、sktopiWiiHBinaryTreeDebugBinaoTree.exeH1951020211122233714282915303122010215221123114297351531完全二叉樹非遞歸后序逅歷結(jié)果：32161?81819941202JL10222521226271362829全二叉樹層次序遍歷統(tǒng)果：1234567891011121314151617181920212223242526272829303132Pressan/keytocontinue總結(jié)這次的課程設(shè)計(jì)我選擇了二義樹的遍歷，因?yàn)闃浣Y(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)課程的典型內(nèi)容，而且綜合使用了多種邏輯結(jié)構(gòu)

32、，具有代表性，可以鍛煉個(gè)人編程能力。在剛開始選題后，我感覺無從下手，一是因?yàn)闆]有實(shí)踐經(jīng)驗(yàn)，二是因?yàn)閷?duì)數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容沒有把握到位，然后在參考一些專業(yè)書籍并且學(xué)習(xí)了之前其他人的課程設(shè)訃，才逐漸可以上手去自己做。在做了一小段后我發(fā)現(xiàn)如果不使用數(shù)組來建立二義樹是很麻煩的一件事，每個(gè)結(jié)點(diǎn)的信息都靠鍵盤輸入是不合理的，于是運(yùn)用了數(shù)組這一數(shù)據(jù)類型。在之后的遞歸算法中，我遇到的最大困難是如何實(shí)現(xiàn)遞歸，為此我參考了一本專業(yè)書籍，學(xué)會(huì)了如何正確使用遞歸方法，這也讓我感覺到學(xué)習(xí)與應(yīng)用是不可分開的。對(duì)于非遞歸算法，我使用了棧結(jié)構(gòu)和隊(duì)列結(jié)構(gòu)，分別用于前序遍歷、中療；、后序遍歷、非遞歸層次序遍歷方法中。使用棧和隊(duì)列的

33、過程中，我在實(shí)踐中乂學(xué)習(xí)了棧和隊(duì)列的一些知識(shí)，提高了各種邏輯結(jié)構(gòu)之間的綜合運(yùn)用能力。在后期測(cè)試階段，我參考了許多課程設(shè)計(jì)案例，他們都運(yùn)用了switch。語句，這樣雖然看著有條理，卻不適合用在二叉樹的遍歷上，因?yàn)楸闅v結(jié)果顯而易見并不十分復(fù)雜，沒有必要使程序復(fù)雜化，因此我采用的是程序運(yùn)行輸出模式?？傮w來說，在本次課程設(shè)訃中，我深刻體會(huì)了再面向?qū)ο蟪绦蛟O(shè)計(jì)中數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方法，既學(xué)到了專業(yè)知識(shí)，也體會(huì)到“溫故知新”的樂趣，因此如果還有課程設(shè)訃我還會(huì)積極參加，在實(shí)踐中鍛煉自己的能力水平。致謝對(duì)我來說這次課程設(shè)計(jì)的機(jī)會(huì)來之不易，首先我的父母辛苦工作，用他們賺到的血汗錢供我讀書，讓我有機(jī)會(huì)接受高等教育。其

34、次，我的課程設(shè)訃指導(dǎo)老師寇老師，冒著嚴(yán)寒每天早早地到機(jī)房為我指導(dǎo)、調(diào)試程序，從沒有一句怨言。再者，我的數(shù)據(jù)結(jié)構(gòu)授課教師周教授，從一開始接觸這門課就不辭辛勞的給我傳授知識(shí)，教我學(xué)的立足社會(huì)的資本。對(duì)你們,我想發(fā)自內(nèi)心的說一句：謝謝你們，辛苦了！參考文獻(xiàn)（I）數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+語言描述）殷人昆清華大學(xué)出版社（2）深入體驗(yàn)C+項(xiàng)H開發(fā)管西京清華大學(xué)出版社（3）C+程序員教程（美）DeiteLP.J.,（美）DeiZHM著北京電子工業(yè)出版社附錄：程序源代碼：/mian()主函數(shù)中：#includenBinaryTree.hH#include#include#includeusingname

35、spacestd;voidvisit(BinTreeNode*t)coutt-dataHH;voidmain()BinaryTreebinTree(O);coutv從數(shù)組數(shù)據(jù)建立完全二義樹:n”;COUt輸入二義樹的元素總個(gè)數(shù)：”；longnum;cinnum;int東CBT=newintnum;cout”n數(shù)組中數(shù)據(jù)為:n；for(inti=0;inum;i+)CBTi=i+1;coutsetw(4)i+1;)coutendl;BinaryTreebinTreel;binTreel.CreateCompBinTree(CBT,num);cout”n完全二義樹前序遍歷結(jié)果:n=binTreel

36、.PreOrder(visit);coutunn完全二叉樹中序遍歷結(jié)果:n；binTreel.InOrder(visit);coutnn完全二叉樹后序遍歷結(jié)果:n；binTreel.PostOrder(visit);coutDn完全二義樹非遞歸前序遍歷結(jié)果:n；binTree1.PreOrder1(visit);coutTnn完全二義樹非遞歸中序遍歷結(jié)果:n”;binTree1.InOrder1(visit);cout”nn完全二義樹非遞歸后序遍歷結(jié)果：n”；binTree1.PostOrder1(visit);coutn完全二義樹層次序遍歷結(jié)果:n；binTree1JevelOrder(vi

37、sit);coutendl;deleteCBT;)包含在頭文件BinaryTree.h中#include#include#includeusingnamespacestd;#includeHLinkedStack.hn#includeHLinkedQueue.hntemplatestructBinTreeNodej樹結(jié)點(diǎn)Tdata;BinTreeNode*leftChild;BinTreeNode*rightChild;BinTreeNode():leftChiId(NULL),rightChild(NULL)BinTreeNode(Tx,BinTreeNode*1=NULL,BinTreeN

38、ode*r=NULL):leftChild(1),rightChild(r)data=x;)；templateclassBinaryTree,叉樹類定義public:BinaryTree():root(NULL)BinaryTree(Tvalue):root(NULL)RefValue=value;)BinaryTree(BinaryTree&s)if(this!=&s)root=Copy(s.root);)-BinaryTree()BinTreeNode*Parent(BinTreeNode*t)return(root=NULLIIroot=t)?NULL:Parent(root,t);)B

39、inTreeNode*LeftChild(BinTreeNode*t)return(t!=NULL)?t-leftChild:NULL;)BinTreeNode*RightChild(BinTreeNode*t)return(t!=NULL)?t-rightChild:NULL;voidPreOrder(void(*visit)(BinTreeNode*t)PreOrder(root,visit);)voidInOrder(void(*visit)(BinTreeNode*t)InOrder(root,visit);)voidPostOrder(void(*visit)(BinTreeNode

40、*t)PostOrder(root,visit);)voidCreateCompBinTree(T*CBT,intnum)建立完全義樹CreateCompBinTree(CBT,num,0,root);)voidlevelOrder(void(*visit)(BinTreeNode*t);層次序遍歷voidPreOrder1(void(*visit)(BinTreeNode*t);非遞歸前序遍歷voidInOrder1(void(*visit)(BinTreeNode*t);非遞歸中序遍歷voidPostOrder1(void(*visit)(BinTreeNode*t);非遞歸后序遍歷fri

41、endistream&operator(istream&in,BinaiyTree&Tree)輸入二叉樹Tree.CreateBinTree(in,Tree.root);returnin;1protected:BinTreeNode*root;二義樹的根指針TRetValue;數(shù)據(jù)輸入停止標(biāo)志voidCreateBinTree(istream&in,BinTreeNode*&subTree);遞歸建立二義樹voidCreateCompBinTree(T*CBT,intnum,intrt,BinTreeNode*&subTree);建立完全二義樹BinTreeNode*Copy(BinTreeN

42、ode*r);復(fù)制二叉樹rvoidTraverse(BinTreeNode*subTree,ostreani&out);tf遍歷輸出voidPreOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t);/前序遍歷voidInOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t);/中序遍歷voidPostOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t);/后序遍歷1;templatevoidBinaryTree:CreateBinTr

43、ee(istream&in,BinTreeNode伙&subTree)私有函數(shù)：以遞歸方式建立二義樹。Titem;if(initein)if(item!=RefVakie)subTree=newBinTreeNode(itern);/CreateRootassert(subTree);CreateBinTree(in,subTree-leftChild);/CreateleftchildtreeCreateBinTree(in,subTree-rightChild);/Createreghtchildtreeelse(subTree=NULL;)templatevoidBinaryTree:C

44、reateCompBinTree(T*CBT,intnum,intrt5BinTreeNode港&subTree)建立完全二義樹if(rt=num)subTree=NULL;elsesubTree=newBinTreeNode(CBTrt);CreateCompBinTree(CBT,num,2*rt+l,subTree-leftChild);CreateCompBinTree(CBT,num,2*rt+2,subTree-rightChild);)templateBinTreeNode*BinaryTree:Copy(BinTreeNode*r)遞歸復(fù)制二叉樹if(!r)returnNULL

45、;BinTreeNode*p=newBinTreeNode(r-data);p-leftChild=Copy(r-leftChiId);p-rightChild=Copy(r-rightChild);returnp;)templatevoidBinaryTree:Traverse(BinTreeNode*subTree,ostream&out)前序遍歷輸出結(jié)點(diǎn)數(shù)據(jù)if(subTree)outsubTree-data*Traverse(subTree-leftChild,out);Traverse(subTree-rightChild,out);)templatevoidBinaryTree:P

46、reOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t)遞歸前序遍歷if(subTree!=NULL)visit(subTree);PreOrder(subTree-leftChild,visit);PreOrder(subTree-rightChild,visit);)templatevoidBinaryTree:InOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t)遞歸中序遍歷if(subTree!=NULL)InOrder(subTree-leftChild,visit);vis

47、it(subTree);InOrder(subTree-rightChild,visit);)templatevoidBinaryTree:PostOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t)遞歸后序遍歷if(subTree!=NULL)PostOrder(subTree-leftChild,visit);PostOrder(subTree-rightChild5visit);visit(subTree);)templatevoidBinaryTree:PreOrderl(void(*visit)(BinTreeNode*t)非遞歸

48、前序遍歷LinkedStackBinTreeNode*S;BinTreeNode*p=root;S.Push(NULL);while(p!=NULL)visit(p);訪問結(jié)點(diǎn)if(p-rightChild!=NULL)S.Push(p-rightChild);預(yù)留右指針在棧中if(p-leftChild!=NULL)p=p-leftChild;進(jìn)左子樹elseS.Pop(p);左子樹為空，由堆棧彈出)templatevoidBinaryTree:InOrderl(void(*visit)(BinTreeNodet)非遞歸中序遍歷LinkedStackBinTreeNode*S;BinTree

49、Node*p二root;while(p!=NULLII!S.IsEmpty()while(p!=NULL)遍歷指針向左下移動(dòng)S.Push(p);該子樹沿途結(jié)點(diǎn)進(jìn)棧p=p-leftChild;if(!S.IsEmpty()棧不空時(shí)退棧S.Pop(p);visit(p);退棧，訪問p=p-rightChild;遍歷指針進(jìn)到右子女templatestructstkNodeBinTreeNode*ptr;樹結(jié)點(diǎn)指針enumL,Rtag;退棧標(biāo)記，必須說明為枚舉變量，tag移到最右邊。這里最好用bool量stkNode(BinTreeNode*N=NULL)構(gòu)造函數(shù)ptr=N;tag=L;)；templ

50、atevoidBinaryTree:PostOrder1(void(*visit)(BinTreeNode*t)非遞歸后序遍歷LinkedStackstkNodeS;stkNodew;BinTreeNode*p=root;p是遍歷指針dowhile(p!=NULL)w.ptr=p;w.tag=stkNode:L;枚舉類型定義在structstkNode中，如定義為全局性就簡(jiǎn)單了S.Push(w);p=p-leftChild;intcontinue1=1;while(continue1&JS.IsEmpty()S.Pop(w);p=w.ptr;switch(w.tag)判斷棧頂?shù)膖ag標(biāo)記casestkNode:L:w.tag二stkNode:R;S.Push(w);continue1=0;p=p-rightChild;break;casestkNode:R:visit(p);