華中科技大學軟件學院文件(編輯修改稿)

　

【文章內容簡介】 遞歸定義。二叉樹可以是空集合，二叉樹結點的子樹 軟件課程設計2010年1月要區分左子樹和右子樹，即使只有一棵子樹也要進行區分，說明它是左子樹，還是右子樹。二叉樹的定義方法:Struct tree { char info。struct tree *left, *right。}(2).存儲結構:存儲結構分為順序存儲結構和鏈式存儲結構。：從樹根起，自上層至下層，每層自左至右的給所有結點編號缺點是有可能對存儲空間造成極大的浪費，在最壞的情況下，一個深度為H且只有H個結點的右單支樹確需要2h1個結點存儲空間。而且，若經常需要插入與刪除樹中結點時，順序存儲方式不是很好！光信0804廖娟U200813197：存儲二叉樹經常用二叉鏈表法(3).遍歷二叉樹：假如以L、D、R分別表示遍歷左子樹、遍歷根結點和遍歷右子樹，遍歷整個二叉樹則有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。若規定先左后右，則只有前三種情況，分別規定為：DLR——先（根）序遍歷，LDR——中（根）序遍歷，軟件課程設計2010年1月LRD——后（根）序遍歷。①．先序遍歷二叉樹的操作定義為： 若二叉樹為空，則空操作；否則 ； ； 。②．中序遍歷二叉樹的操作定義為： 若二叉樹為空，則空操作；否則 ； ； 。③．后序遍歷二叉樹的操作定義為： 若二叉樹為空，則空操作；否則 ； ； 。 程序結構及功能劃分(1).廖娟主要分為主函數、創建二叉樹子函數、二叉樹查詢子函數、二叉樹打印子函數四個部分。其基本功能分塊，如下圖所示： 光信0804廖娟U200813197(2).廖娟 在 廖娟 的基礎上進行了一些算法改進，進行了簡單的界面設計，能夠實現友好的交互，系統用戶進入界面控制后，對不同的功能操作提示不同，此外加入了二叉排序樹的前序遍歷程序、中序遍歷程序和后序遍歷程序。①．先序遍歷源代碼：void PreorderTraversal(struct tree *root){ if(root==0)return。printf(“%c”,rootinfo)。軟件課程設計2010年1月PreorderTraversal(rootleft)。PreorderTraversal(rootright)。} ②．中序遍歷源代碼：void InorderTraversal(struct tree *root){ if(!root)return。InorderTraversal(rootleft)。printf(“%c”,rootinfo)。InorderTraversal(rootright)。} ③．后序遍歷源代碼：void PostorderTraversal(struct tree *root){ if(!root)return。PostorderTraversal(rootleft)。PostorderTraversal(rootright)。printf(“%c”,rootinfo)。} 光信0804廖娟U200813197 程序流程廖娟： 軟件課程設計2010年1月創建二叉樹的流程圖如下： 光信0804廖娟U200813197二叉樹查詢的流程圖如下: 軟件課程設計2010年1月二叉樹打印的流程圖如下: 光信0804廖娟U200813197軟件測試 測試環境Microsoft Visual C++ 廖娟 的測試過程但是在測試的過程中也發現了一些問題，設計示例給出的源代碼中存在幾個問題在下圖所示操作中暴露出來了：軟件課程設計2010年1月具體的解決方案見算法改進。 廖娟 的測試過程輸入50個數字(或字母)，對 廖娟 進行測試。(1).程序運行前的初始界面 光信0804廖娟U200813197(2).輸入數據及二叉樹打印的畫面(3).選擇操作的提示畫面 軟件課程設計2010年1月(4).程序測試時的畫面①．選擇1，進行先序遍歷； ②．選擇2，進行中序遍歷； ③．選擇3，進行后序遍歷；④．選擇4，進行查詢結點，再輸入要查詢的結點e，找到了，輸出：Successful search！!key=e繼續輸入w，同樣查詢成功； ⑤．輸入m，沒找到，輸出結果：Search Failure！!光信0804廖娟U200813197⑥．再次選擇3，進行后序遍歷，與③輸出相同；再次選擇2，進行中序遍歷，與②輸出相同； ⑦．再次選擇4，進行查詢結點，運行結果正常； ⑧．再次選擇1，進行先序遍歷，與①輸出相同； ⑨．選擇8，輸入錯誤，沒有對應的操作，輸出：您 的 輸 入 有 誤，請 重 新 輸 入！!⑩．選擇5，進行退出操作，輸出：光 信 0 8 0 4 ———— 廖 娟0 1 0 年 1 月軟件課程設計2010年1月算法改進在完成第4項選做項目時，程序前面部分的創建、查詢、打印二叉樹的算法仍采用已給出的設計示例中的算法，但是在測試過程中發現存在問題。光信0804廖娟U200813197(1).問題一：第一次先序遍歷的輸出結果為：edaf第二次先序遍歷的輸出結果為：f 經過觀察及調試發現問題在于查詢二叉樹子函數，其中root是根結點，運行查詢后root就被移動了，所以再次要求先序遍歷的結果就與第一次先序遍歷的結果不同。未改動前源代碼如下： 軟件課程設計2010年1月(2).問題二：設計示例中給出的函數運行后，沒有退出的方式，即沒有出口，程序無法正常退出。(1).問題一改進方案：函數內部定義一個指針tree *t，用 *t指向根結點，這樣進行查詢操作后根結點就不會移動了。改動后源代碼如下： 光信0804廖娟U200813197(2).問題二改進方案：在switch語句中增加：case 5:printf(“光 信 0 8 0 4 ———— 廖 娟nn”)。printf(“ 0 1 0 年 1 月nn”)。return。來實現退出程序的操作，具體解決方案見廖娟 的源代碼。軟件課程設計2010年1月開發體會剛剛拿到軟件課程設計的題目時，我震驚了，二叉樹？這是什么東西，上學期學習C語言的時候好像沒學到二叉樹啊。聽了老師的介紹才知道做這個題目的軟件課程設計還要先學習一下數據結構中關于二叉樹部分的知識，當時我真的是有些不知所措，本就不怎么好的C語言加上完全不會的數據結構二叉樹使我開始懷疑：三個星期后我可以完成這份關于二叉樹的查找的軟件課程設計嗎？最初的幾天也確實很沒有頭緒，只是想著想把老師給的資料都看了，看完了之后走一步算一步吧，可是看完了之后發現仍然沒有很大的收獲，連怎么二叉樹到底有什么用都不知道，對于這個題目依然是十分陌生。可是時間緊迫啊，于是找了位學習過數據結構的同學借了本數據結構的書，研究了一番，在加上在網上搜索了一番終于有些頭緒了，知道這份課設到底要我們做什么了！接下來的幾天，隨著了解的加深，自己開始慢慢的做課設了，當然從和同學的交流中，我也學到了很多。這之后我一步步的完成了對設計示例的注釋，對遞歸算法的理解，以及先序遍歷、中序遍歷、后序遍歷程序的書寫，最終完成了程序的開發。程序開發中我記憶最深刻的就是編寫選擇操作的提示界面和初始界面的時候，為了使界面更加友好，加入了一些人性化的語句，以及為了出現歡迎界面進行的許多次試驗，慢慢的我覺得這個過程十分有趣，看著自己編排的界面出現在面前心中還是有些許成就感的。當然除了這些還有很令我頭疼的 光信0804廖娟U200813197程序調試過程：在程序的調試階段，發現程序中有許多問題，有的根本不知道從哪入手解決問題，甚至不知道為什么會出現錯誤，也因此耗費了很多時間，讓我苦悶了很久。在這段時間里，因為有軟件課程設計，讓我學到了很多知識，收獲了很多我，自我感覺自己解決問題的能力提高了，并且掌握了軟件開發的一些基本的方法和技巧。還記得寫課設報告的時候，花了一天的時間把報告里面的所有圖都畫完了，從剛開始的不會用畫圖軟件，到后來慢慢摸索最后熟練運用，畫圖的速度是越來越快了，讓我后來甚是欣慰。經過了這一次的軟件課程設計，我感受到了C語言的魅力，也深切的體會到了“學海無涯”這四個字的分量。在以后的日子里，我所需要學習的東西還有很多很多，應了那句“書山有路勤為徑，學海無涯苦作舟。” 軟件課程設計2010年1月附錄：源代碼清單廖娟 include /* C++頭文件，實現輸入輸出的頭文件*/ include/* 定義二叉樹結構*/ struct tree{char info。// 定義char型變量，存放數據struct tree *left,*right。// 左子樹指針，右子樹指針}。/* 定義結構指針變量，作用創建二叉樹*/ struct tree *create_btree(struct tree *root,struct tree *r,char info)。/* 定義結構指針變量，作用查詢數據*/ struct tree *search_btree(struct tree *root,char key)。/* 定義子函數，作用打印二叉樹*/ void prin