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

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

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

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

4、62概要設計71 .1總體功能結(jié)構72 .2數(shù)據(jù)結(jié)構部分設計72.2.1結(jié)點結(jié)構72.2.2二叉樹結(jié)構83詳細設計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é)構193.6.1功能原理193.6.2算法

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

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

7、中序遍歷：遞歸方法、非遞歸方法3)前序遍歷：遞歸方法、非遞歸方法4)后序遍歷：遞歸方法、非遞歸方法5)棧結(jié)構使用：遍歷時輸入臨時變量以保存6)隊列結(jié)構使用：完全二叉樹遍歷時用以存儲數(shù)據(jù)2. 2數(shù)據(jù)結(jié)構部分設計2.2.1結(jié)點結(jié)構一叉樹結(jié)點結(jié)構中包數(shù)據(jù)域(data),指針域(*leftChild,*rightChild)o結(jié)點結(jié)構的代碼如下：structBinTreeNode樹結(jié)點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é)構結(jié)點包含數(shù)據(jù)域(data),指針域link),實現(xiàn)代碼如下:structStackNode棧結(jié)點Tdata;StackNode*link;StackNode(Td=0,StackNode*next二NULL):link(next),data(d);隊列結(jié)構結(jié)點包含數(shù)據(jù)域(data),指針域(*link),實現(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é)構二叉樹包含了遞歸、非遞歸建樹過程，遞歸、非遞歸的前序遍歷、中序遍歷、后續(xù)遍歷過程。二義樹的類定義包含各種操作，實現(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é)構的定義中，包含了對數(shù)據(jù)的入棧、出棧、清空等基本操作，實現(xiàn)代碼如下templateclassLinkedStackprivate:StackNode*top;public:LinkedStackO:top(NULL)無頭結(jié)點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;)隊列的類定義，實現(xiàn)了對數(shù)據(jù)的入隊、出隊操作，實現(xiàn)代碼如下：template(typenameTclassLinkedQueue無頭結(jié)點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 功能描述二義樹是程序的核心，如何合理的建立至關重要。本實例中使用遞歸和非遞歸方法分別建立二義樹，二義樹的數(shù)據(jù)來源于程序開始時建立的數(shù)組。建立后的二叉樹保存，并且留作之后的遍歷使用。3.1.2 算法原理本實例使用的是完全二叉樹，首先

16、建立頭結(jié)點，并且保存數(shù)據(jù)，然后根據(jù)遞歸方法，分別建立其左右孩子結(jié)點，且左右孩子結(jié)點的指針域指向空。3.1.3 具體程序以遞歸方式建立二叉樹，每次建立一個結(jié)點后，將其左右孩子指針域置空，成為葉子結(jié)點。具體實現(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é)果輸出，達到前序便利的目的，方便數(shù)據(jù)的使用。3. 2.2算法原理前序遍歷使用了遞歸與非遞歸兩種方法，在程序頭文件中定義了兩個函數(shù)分別實現(xiàn)其功能。遞歸時，輸出第一個結(jié)點數(shù)據(jù)時，找到數(shù)據(jù)，然后找到其后面的數(shù)據(jù)，然后依次遞歸輸出。非遞歸時，使用棧和隊列結(jié)構，將部分數(shù)據(jù)保存在?；蜿犃兄校却龑?shù)據(jù)放到合適位置。3. 2.3具體程序1)遞歸算法實現(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)非遞歸算法實現(xiàn):templatevoidBinaryTree：:PreOrderl(void(*visit)(BinTreeNode*t)LinkedStackBinTreeNode*S;BinTreeNode*p二root:S.Push(NULL);while(p!=NULL)visit

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

21、部分數(shù)據(jù)保存在棧與隊列中，等待將數(shù)據(jù)放到合適位置。3.3.3具體程序1)遞歸算法實現(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)非遞歸算法實現(xiàn)：templatevoidBinaryTree:InOrderl(void(水visit)(BinTreeNode*t)非

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

23、在程序頭文件中定義了兩個函數(shù)分別實現(xiàn)其功能。遞歸時，輸出第一個結(jié)點數(shù)據(jù)時，找到數(shù)據(jù)，然后依次找到其后面的數(shù)據(jù)，然后依次遞歸輸出。非遞歸時，使用棧和隊列結(jié)構，將部分數(shù)據(jù)保存在棧與隊列中，等待將數(shù)據(jù)放到合適位置。3.4.3具體程序1)遞歸算法實現(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)非遞歸算法實現(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中，如定義為全局性就簡單了S.Push(w);p=p-leftChild;)intcontinuel=1;while(continuel&!SIsEmpty()SPop(w);p=w

25、.ptr;switch(w.tag)判斷棧頂?shù)膖ag標記casestkNode:L:w-tag=stkNode:R;SPush(w);continuel=0;p二p-rightChild;break;casestkNode:R:visit(p):break;while(!S.IsEmptyO);繼續(xù)遍歷其他結(jié)點coutendl:)3.5層次序非遞歸遍歷3.5.1功能原理層次序非遞歸遍歷，依據(jù)的是遞歸原理，每次遍歷一個結(jié)點后，同時讓其左右孩子入隊，以便達到層次序的目的。3.5.2算法原理每次遍歷完一個結(jié)點后，檢查該結(jié)點是否為葉子結(jié)點，如果是葉子結(jié)點則繼續(xù)下一結(jié)點的遍歷，否則其左右孩子入隊，繼續(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é)構3. 6.1功能原理運用棧結(jié)構，在非遞歸算法中，未輸出的數(shù)據(jù)暫時存入棧中，依據(jù)先進后出原貝IJ,方便了二叉樹的遍歷。4. 6.2算法原理二叉樹的結(jié)點信息，保存在棧中。第一個入棧的數(shù)據(jù)元素保存在棧底，后進棧的在上方，現(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隊列結(jié)構3. 7.1功能原理運用隊列結(jié)構，在層次序遍歷算法中，未輸出的數(shù)據(jù)暫時存入隊列中，依據(jù)先進先出原則，方便了二叉樹的遍歷。4. 7.2算法原理層次序遍歷二義樹信息時，二義樹的結(jié)點信息保存在隊列中。第一個入隊的數(shù)據(jù)元素保存隊首，后入隊的元素依次連接上，先入隊的先出隊。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)試與操作說明操作說明：當程序運行后，會在控制臺提示一下文字：”從數(shù)組數(shù)據(jù)建立完全二義樹：”，“輸入二叉樹的元素總個數(shù)：”，然后從鍵盤輸入二叉樹元素個數(shù)，緊接著系統(tǒng)會自動運行，得到各種遍歷結(jié)果。運行截圖：完全二義樹32個元素時的運行截圖?C:UsersVRADesktopiAAiHABinaryTreeDebugBinarrTree.exenMC:UsersVRADe

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

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

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

34、次，我的課程設訃指導老師寇老師，冒著嚴寒每天早早地到機房為我指導、調(diào)試程序，從沒有一句怨言。再者，我的數(shù)據(jù)結(jié)構授課教師周教授，從一開始接觸這門課就不辭辛勞的給我傳授知識，教我學的立足社會的資本。對你們,我想發(fā)自內(nèi)心的說一句：謝謝你們，辛苦了！參考文獻（I）數(shù)據(jù)結(jié)構（用面向?qū)ο蠓椒ㄅcC+語言描述）殷人昆清華大學出版社（2）深入體驗C+項H開發(fā)管西京清華大學出版社（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輸入二義樹的元素總個數(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é)點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ù)輸入停止標志voidCreateBinTree(istream&in,BinTreeNode*&subTree);遞歸建立二義樹voidCreateCompBinTree(T*CBT,intnum,intrt,BinTreeNode*&subTree);建立完全二義樹BinTreeNode*Copy(BinTreeN

42、ode*r);復制二叉樹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)遞歸復制二叉樹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é)點數(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é)點if(p-rightChild!=NULL)S.Push(p-rightChild);預留右指針在棧中if(p-leftChild!=NULL)p=p-leftChild;進左子樹elseS.Pop(p);左子樹為空，由堆棧彈出)templatevoidBinaryTree:InOrderl(void(*visit)(BinTreeNodet)非遞歸中序遍歷LinkedStackBinTreeNode*S;BinTree

49、Node*p二root;while(p!=NULLII!S.IsEmpty()while(p!=NULL)遍歷指針向左下移動S.Push(p);該子樹沿途結(jié)點進棧p=p-leftChild;if(!S.IsEmpty()棧不空時退棧S.Pop(p);visit(p);退棧，訪問p=p-rightChild;遍歷指針進到右子女templatestructstkNodeBinTreeNode*ptr;樹結(jié)點指針enumL,Rtag;退棧標記，必須說明為枚舉變量，tag移到最右邊。這里最好用bool量stkNode(BinTreeNode*N=NULL)構造函數(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中，如定義為全局性就簡單了S.Push(w);p=p-leftChild;intcontinue1=1;while(continue1&JS.IsEmpty()S.Pop(w);p=w.ptr;switch(w.tag)判斷棧頂?shù)膖ag標記casestkNode:L:w.tag二stkNode:R;S.Push(w);continue1=0;p=p-rightChild;break;casestkNode:R:visit(p);