數(shù)據(jù)結構課程設計報告--二叉樹的算法

1、<p><b>　　課程設計報告</b></p><p>　　課程名稱：數(shù)據(jù)結構課程設計</p><p>　　設計題目： 二叉樹的算法 </p><p>　　院 系： 計算機工程學院 </p><p>　　專 業(yè)：

2、計算機科學與技術 </p><p><b>　　目錄</b></p><p><b>　　1需求分析1</b></p><p>　　1.1課程設計題目、任務及要求1</p><p>　　1.2課程設計思想1</p><p>　　1.3軟硬件運行環(huán)境及

3、開發(fā)工具1</p><p><b>　　2概要設計2</b></p><p>　　2.1各功能模塊流程圖2</p><p>　　2.2 創(chuàng)建二叉樹2</p><p>　　2.3二叉樹的遞歸遍歷算法（先、中、后）2</p><p>　　2.3.1先序遍歷2</p><

4、p>　　2.3.2中序遍歷2</p><p>　　2.3.3后序遍歷2</p><p>　　2.4二叉樹的非遞歸遍歷算法（前、中、后）3</p><p>　　2.4.1非遞歸的先序遍歷算法3</p><p>　　2.4.2非遞歸的中序遍歷算法3</p><p>　　2.4.3非遞歸的后序遍歷算法3&l

5、t;/p><p>　　2.5層次序遍歷3</p><p><b>　　2.6退出3</b></p><p>　　3詳細設計和實現(xiàn)3</p><p>　　3.1主要功能模塊設計3</p><p>　　3.2主程序設計4</p><p>　　4調(diào)試與操作說明6</

6、p><p><b>　　4.1程序調(diào)試6</b></p><p>　　4.2程序操作說明6</p><p><b>　　總 結9</b></p><p><b>　　致謝10</b></p><p><b>　　參考文獻10</

7、b></p><p><b>　　1需求分析</b></p><p>　　1.1課程設計題目、任務及要求</p><p>　　二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)，應包含建樹的實現(xiàn)。要求：遍歷的內(nèi)容應是多樣的。</p><p><b>　　1.2課程設計思想<

8、/b></p><p>　　首先按先序次序建立一個二叉樹，遞歸遍歷，包括先序、中序、后序遞歸遍歷。三種不同次序的遍歷二叉樹的遞歸算法的結構相似，只是訪問結點及遍歷左子樹、遍歷右子樹的先后次序不同而已。在遞歸執(zhí)行過程中，先序遍歷是每進入一層遞歸調(diào)用時先訪問根結點，再依次向它的左、右子樹遞歸調(diào)用。中序遍歷是在從左子樹遞歸調(diào)用退出時訪問根結點，然后向它的右子樹遞歸調(diào)用。后序遍歷是在從左、右子樹遞歸調(diào)用后，再訪問根

9、結點。</p><p>　　把一個遞歸過程改為非遞歸過程一般需要利用棧，記錄遍歷時的回退路徑。利用棧的先序遍歷二叉樹（非遞歸）：每次訪問一個結點后，在向左子樹遍歷下去之前，利用這個棧記錄該結點的右子女（如果有的話）結點的地址，以便在左子樹退回時可以直接從棧頂取得右子樹的根結點，繼續(xù)右子樹的先序遍歷。利用棧的中序遍歷二叉樹（非遞歸）：首先訪問的是中序下的一個結點，它位于從根開始沿左子樹鏈走到最左下角的結點，該結點的

10、左子樹指針為空。訪問它的數(shù)據(jù)之后，再遍歷該結點的右子樹。此右子樹又是二叉樹，重復執(zhí)行上面的過程，直到該子樹遍歷完。結束條件為：棧為空的同時遍歷指針也為空。利用棧的后序遍歷二叉樹（非遞歸）：在遍歷完左子樹是還不能訪問根結點，需要再遍歷右子樹。右子樹遍歷完后才訪問根結點。所以在棧記錄中必須注明剛才是在左子樹還是右子樹中。，在算法中首先使用棧暫存根結點地址，再向左子樹遍歷下去，此時根結點的tag=1。訪問完左子樹結點并退回時，還要遍歷根的右子

11、樹，此時改根結點的tag=2.在從右子樹中退出時才訪問位于棧頂?shù)母Y點的值。</p><p>　　層次序遍歷從二叉樹的根結點開始，自上而下，自左向右分層依次訪問樹中的各個結點。訪問二叉樹的處理需要利用一個隊列。在訪問二叉樹的某一層結點是，把下一層結點指針預先記憶在隊列中，利用隊列安排逐層訪問的次序。每訪問一個結點時，將它的子女依次加到隊列的隊尾，然后再訪問已在隊列隊頭的結點。這樣可以實現(xiàn)二叉樹結點的按層訪問。&l

12、t;/p><p>　　1.3軟硬件運行環(huán)境及開發(fā)工具</p><p>　　Windows2000以上操作系統(tǒng)、Microsoft Visual C++ 6.0</p><p><b>　　2概要設計</b></p><p>　　2.1各功能模塊流程圖</p><p>　　圖2.1.2主函數(shù)流程圖(b)

13、</p><p><b>　　2.2 創(chuàng)建二叉樹</b></p><p>　　(1)定義二叉樹結點值的類型為字符型。(2)結點個數(shù)不超過20個。(3)按先序次序輸入，構造二叉鏈表表示的二叉樹T，空格表示空樹。</p><p>　　2.3二叉樹的遞歸遍歷算法（先、中、后）</p><p><b>　　2.3.1先

14、序遍歷</b></p><p>　　(1)訪問根結點。(2)先序遍歷根結點的左子數(shù)。(3)先序遍歷根結點的右子數(shù)。</p><p><b>　　2.3.2中序遍歷</b></p><p>　　(1)先序遍歷根結點的左子數(shù)。(2)訪問根結點。(3)先序遍歷根結點的右子數(shù)。</p><p><b>　　

15、2.3.3后序遍歷</b></p><p>　　(1)先序遍歷根結點的左子數(shù)。(2)先序遍歷根結點的右子數(shù)。(3)訪問根結點。</p><p>　　2.4二叉樹的非遞歸遍歷算法（前、中、后）</p><p>　　2.4.1非遞歸的先序遍歷算法</p><p>　　(1)訪問結點的數(shù)據(jù)域。(2)指針指向p的左孩子結點。(3)從棧中彈

16、出棧頂元素。 (4)指針指向p的右孩子結點。</p><p>　　2.4.2非遞歸的中序遍歷算法</p><p>　　(1)指針指向p的左孩子結點。(2)從棧中彈出棧頂元素。(3)訪問結點的數(shù)據(jù)域。(4)指針指向p的右孩子結點。</p><p>　　2.4.3非遞歸的后序遍歷算法</p><p>　　bt是要遍歷樹的根指針，后序遍歷要求在遍歷

17、完左右子樹后，再訪問根。需要判斷根結點的左右子樹是否均遍歷過?？刹捎脴擞浄ǎY點入棧時，配一個標志一同入棧。</p><p>　　首先將bt和標記(為1)入棧，遍歷左子樹；返回后，修改棧頂標記為2，遍歷右子樹；最后訪問根結點。</p><p><b>　　2.5層次序遍歷</b></p><p>　　(1)訪問該元素所指結點。(2)若該元素所指

18、結點的左右孩子結點非空，則該元素所指結點的左孩子指針和右孩子指針順序入隊。</p><p><b>　　2.6退出</b></p><p><b>　　3詳細設計和實現(xiàn)</b></p><p>　　3.1主要功能模塊設計</p><p>　　程序主要設計了五個功能：首先是創(chuàng)建二叉樹, 按先序次序輸入

19、，構造二叉鏈表表示的二叉樹T，#表示空樹。</p><p>　　其余還有四個模塊，包括：二叉樹的遞歸遍歷算法（先序、中序、后序）；層次序遍歷；二叉樹的非遞歸遍歷算法（先序、中序、后序）；退出。</p><p><b>　　主函數(shù)流程如下：</b></p><p>　　圖3.1.1主函數(shù)流程圖（a）</p><p><

20、;b>　　3.2主程序設計</b></p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　BiTree T;</b></p><p><b>　　T=NULL;</b></p><p

21、>　　int select;</p><p>　　//cout<<"請按先序次序輸入各結點的值，以#表示空樹(輸入時可連續(xù)輸入):"<<endl;</p><p>　　// CreateBiTree(T);</p><p><b>　　while(1)</b></p><p&

22、gt;<b>　　{</b></p><p>　　cout<<"\n請輸入要執(zhí)行的操作的序號:\n";</p><p>　　cout<<"1.創(chuàng)建二叉樹\n";</p><p>　　cout<<"2.二叉樹的遞歸遍歷算法（前、中、后）\n";<

23、/p><p>　　cout<<"3.二叉樹的非遞歸遍歷算法（前、中、后）\n";</p><p>　　cout<<"4.二叉樹的層次遍歷算法"; </p><p>　　cout<<"\n0.退出\n";</p><p>　　cin>>se

24、lect;</p><p>　　switch(select)</p><p><b>　　{</b></p><p>　　case 0:return;</p><p><b>　　case 1:</b></p><p>　　cout<<"先序次序輸入二叉

25、樹，以#表示空樹(輸入時可連續(xù)輸入):"<<endl;</p><p>　　CreateBiTree(T);</p><p><b>　　break;</b></p><p><b>　　case 2:</b></p><p>　　if(!T) cout<<&quo

26、t;未建立樹";</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　cout<<"\n先序遍歷:\n";</p><p>　　PreOrderTraverse(T);</p><p&

27、gt;　　cout<<"\n中序遍歷:\n";</p><p>　　InOrderTraverse(T);</p><p>　　cout<<"\n后序遍歷:\n";</p><p>　　PostOrderTraverse(T);</p><p><b>　　}</

28、b></p><p><b>　　break;</b></p><p><b>　　case 3:</b></p><p>　　if(!T) cout<<"未建立樹";</p><p><b>　　else</b></p>&

29、lt;p><b>　　{</b></p><p>　　cout<<"\n先序遍歷:\n";</p><p>　　NRPreOrder(T);</p><p>　　cout<<"\n中序遍歷:\n";</p><p>　　NRInOrder(T);<

30、;/p><p>　　cout<<"\n后序遍歷:\n";</p><p>　　NRPostOrder(T);</p><p><b>　　}</b></p><p><b>　　break;</b></p><p><b>　　case

31、4:</b></p><p>　　cout<<"\n層序遍歷:\n";</p><p>　　LevelOrderTraverse(T);</p><p><b>　　break;</b></p><p><b>　　default:</b></p&g

32、t;<p>　　cout<<"請確認選擇項:\n";</p><p>　　}//end switch</p><p>　　}//end while </p><p><b>　　}</b></p><p><b>　　4調(diào)試與操作說明</b></p

33、><p><b>　　4.1程序調(diào)試</b></p><p>　　圖4.1.1 調(diào)試界面</p><p>　　在程序調(diào)試過程當中，編譯時并沒有報錯，但是運行時總是出錯，在查閱資料和老師的幫助下，發(fā)現(xiàn)創(chuàng)建二叉樹的語句出現(xiàn)了問題。</p><p><b>　　4.2程序操作說明</b></p>

34、<p>　?。?）選擇要執(zhí)行的操作，第一步創(chuàng)建二叉樹。按先序次序輸入各結點的值，以#號表示空樹。</p><p>　　圖4.2.1運行界面一</p><p>　?。?）二叉樹的遞歸遍歷</p><p>　　圖4.2.2運行界面二</p><p>　?。?）二叉樹的非遞歸遍歷</p><p>　　圖4.2.3

35、運行界面三</p><p>　　（4）二叉樹的層次遍歷</p><p>　　圖4.2.4運行界面四</p><p><b>　?。?）退出</b></p><p>　　圖4.2.5運行界面五</p><p><b>　　總 結</b></p><p>

36、;　　通過這次的程序設計，我充分掌握了二叉樹的一些基本算法，懂得了如何先序創(chuàng)建二叉樹，二叉樹的三種遞歸遍歷算法，三種非遞歸遍歷算法以及層次序遍歷的算法。</p><p>　　通過一周的課程設計，我已經(jīng)會用先序次序完成二叉樹的創(chuàng)建，對二叉樹的多種遍歷也有了更多、更廣泛的理解。二叉樹遍歷的方法是構造各種二叉樹操作的基礎，有很多操作如果選用恰當?shù)谋闅v方法可以簡化實現(xiàn)。對于線性結構而言，遍歷是一種基本的操作，而二叉樹是一

37、種非線性結構，每個結點可能不止一個直接后繼，這樣必須規(guī)定遍歷的規(guī)則，按此規(guī)則遍歷二叉樹，最后得到二叉樹結點的一個線性序列。因而，二叉樹的結點存在關于這個關于這個線性序列的前驅(qū)和后繼。</p><p>　　在設計的過程中，我查閱了大量的資料，掌握理論知識的同時，也吸取了很多老師和同學的方法。一些理論的知識平時可能比較難以理解，但通過課程設計，讓我們更主動的去理解，去查閱有關知識，從而掌握得更加透徹。</p&g

38、t;<p><b>　　致 謝</b></p><p>　　本次數(shù)據(jù)結構課程設計我從指導老師身上學到了很多東西，讓我收獲很多。老師們認真負責的工作態(tài)度，嚴謹?shù)闹螌W精神和深厚的理論水平都使我收益匪淺。無論在理論上還是在實踐中，他們都給了我很大的幫助，使我得到很大的提高，排除了各種困難，這對于我以后的學習甚至工作都有一種巨大的幫助，在此感謝他耐心的輔導。同學們給予了我很多意見，這

39、次我能順利完成課程設計，少不了他們的幫助，在此向給予我?guī)椭耐瑢W說聲謝謝。在撰寫課程設計報告階段，老師審閱我們的報告，而且提出了許多意見，如果沒有他的指導，我們就不能較好的完成這次課題設計的任務。</p><p>　　我還要感謝對我有所教導的老師，他們孜孜不倦的教誨不但讓我和同學們學到了很多知識，而且讓我掌握了動手實踐學習的方法，還提供了這么好的實踐機會，更教會了我做人處事的道理，在此表示感謝。同時，在編程過程中

40、還有同學們給了我?guī)椭徒ㄗh，這里一并表示感謝。</p><p><b>　　參考文獻</b></p><p>　　1 殷人昆.數(shù)據(jù)結構：面向?qū)ο蠓椒ㄅcC++語言描述.清華大學出版社，2007</p><p>　　2 陳慧南．數(shù)據(jù)結構與算法 C++ 語言描述．高等教育出版社 2005</p><p>　　3 嚴蔚敏，