數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--二叉樹的算法

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

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

3、開(kāi)發(fā)工具1</p><p><b>　　2概要設(shè)計(jì)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詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)3</p><p>　　3.1主要功能模塊設(shè)計(jì)3</p><p>　　3.2主程序設(shè)計(jì)4</p><p>　　4調(diào)試與操作說(shuō)明6</

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

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

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

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

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

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

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

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

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

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

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

17、完左右子樹后，再訪問(wèn)根。需要判斷根結(jié)點(diǎn)的左右子樹是否均遍歷過(guò)?？刹捎脴?biāo)記法，結(jié)點(diǎn)入棧時(shí)，配一個(gè)標(biāo)志一同入棧。</p><p>　　首先將bt和標(biāo)記(為1)入棧，遍歷左子樹；返回后，修改棧頂標(biāo)記為2，遍歷右子樹；最后訪問(wèn)根結(jié)點(diǎn)。</p><p><b>　　2.5層次序遍歷</b></p><p>　　(1)訪問(wèn)該元素所指結(jié)點(diǎn)。(2)若該元素所指

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

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

20、;b>　　3.2主程序設(shè)計(jì)</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<<"請(qǐng)按先序次序輸入各結(jié)點(diǎn)的值，以#表示空樹(輸入時(shí)可連續(xù)輸入):"<<endl;</p><p>　　// CreateBiTree(T);</p><p><b>　　while(1)</b></p><p&

22、gt;<b>　　{</b></p><p>　　cout<<"\n請(qǐng)輸入要執(zhí)行的操作的序號(hào):\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、樹，以#表示空樹(輸入時(shí)可連續(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<<"請(qǐng)確認(rèn)選擇項(xiàng):\n";</p><p>　　}//end switch</p><p>　　}//end while </p><p><b>　　}</b></p><p><b>　　4調(diào)試與操作說(shuō)明</b></p

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

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

35、運(yùn)行界面三</p><p>　?。?）二叉樹的層次遍歷</p><p>　　圖4.2.4運(yùn)行界面四</p><p><b>　　（5）退出</b></p><p>　　圖4.2.5運(yùn)行界面五</p><p><b>　　總 結(jié)</b></p><p>

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

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

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

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

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