1、數據結構課程設計報告姓 名班 級學 號指導老師課程設計目的培養學生用學到的書本知識解決實際問題的能力； 培養實際工作所需要的動 手能力；培養學生以科學理論和工程上能力的技術，規范地開發大型、復雜、高 質量的應用軟件和系統軟件具有關鍵性作用； 通過課程設計的實踐，學生可以在 程序設計方法、上機操作等基本技能和科學作風方面受到比較系統和嚴格的訓 練。二、課程設計要求1) 學生必須仔細閱讀數據結構課程設計方案，認真主動完成課程設計的 要求。有問題及時主動通過各種方式與教師聯系溝通。2) 學生要發揮自主學習能力，充分利用時間，安排好課程設計的時間計劃， 并在課程設計過程中不斷檢測自己的計劃完成情況，及

2、時向教師匯報。3) 課程設計按照教學計劃需要一周時間完成， 一周中每天至少要上兩小時的 上機來調試C或C+語言設計的程序，總共至少要上機調試程序 10小時。屬教 師安排上機時間學生不得缺席。三、課程設計內容二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷 算法的實現，應包含建樹的實現。四、課程設計原理1. 設計思想以廣義表格式輸入一個二叉樹，將其接收至一維數組中，利用棧結構建立二 叉鏈表樹；通過先、中、后訪問根結點遞歸算法遍歷二叉樹；利用棧結構依次將 結點入棧、出棧實現二叉樹的非遞歸遍歷算法； 利用隊列的入隊、出隊操作實現 二叉樹的層次遍歷。例如：a(c(,d)，f(g,)建

3、立如下圖所示二叉樹。2. 數據結構typedef BTREENODEPTR elemtype;1) 隊列數據類型定義typedef structelemtype *elem;int front,rear;int size;SqQueue;2) 棧數據類型定義typedef struct stack_tagelemtype *elem;int top;int size;SQSTACK;3) 二叉樹數據類型定義typedef struct btreenodechar data;struct btreenode *lchild,*rchild; BTREENODE,*BTREENODEPTR,*BT

4、REE;3. 主要模塊設計BTREE CreateBtree1(char *str) ；/創建二叉樹 void PreOrder(BTREE root) ； /先序遞歸遍歷二叉樹 void InOrder(BTREE root) ； /中序遞歸遍歷二叉樹 void PostOrder(BTREE root) ； /后序遞歸遍歷二叉樹void PreOrder_1(BTREE root) ； /先序非遞歸遍歷二叉樹void InOrder_1(BTREE root) ； /中序非遞歸遍歷二叉樹void PostOrder_1(BTREE root) ； /后序非遞歸遍歷二叉樹void Layer

5、Order(BTREE root) ； /層次遍歷其他模塊包括棧的初始化及其基本操作和隊列的初始化及基本操作1）二叉樹的建立其中mark的值1、2、3、4分別指stri為字母、（'，'）;tag為左、右孩子的標志；2）二叉樹的遞歸遍歷（以先序遍歷為例）3）二叉樹的非遞歸遍歷（以先序遍歷為例）4）二叉樹的層次遍歷則該元素所指訪問元素所指結點，若該元素所指結點的左右孩子結點非空, 結點的左孩子指針和右孩子指針順序入隊。初始化隊列，root入隊NYf-'p->lchlld 入隊p->lchild!=nullNYp->rchlld 入p->lchild!

6、=null結束 =- = = _= 二二歷厲歷; 歷歷歷遍遍遍盯 r-偏遍遍3口日"用 薛歸歸歸遞遞遞歷斛 揉遞遞遞“先中后<> 1234-567五、運行結果1.建立二叉樹、"請輸入一棵二叉樹：a<c<,d>,£<«,>>2.先序遍歷請選擇;ia c d f g -沁擇I4a c d f g請選棒:3.中序遍歷""請選擇:2G d a g f 請選棒:5c d a sr F 請選帛4.后序遍歷""請選擇:3d c g f a""請選擇:6d c S

7、T f a 請選擇:5.層次遍歷遍 遍 逋 歸 3 歸歷 歷 歷 遍 遍歷=歷“"歷一遍 遍歸>3歷 歷 歷遍歷. 屁 歷=遍 遍 遍 歸 3 '3if歷 歷 歷遍歷-一 歷 = 陌歸邊遞遞歷 “知曙%J中后層 « _ 豐 d -1234567.葫歸歸歸遞遞遞歷関 折遞遞遞：茸 一一先中后先中后昌瓏 123斗5E7-女芻歸歸歸遞遞遞歷一詩遞遞遞! 丄 =1234S67.請選擇: ?a c f d gA-“謫選擇:6.退出程序FKRH主菜單= = = = = = =i-%JT>?3 遍歷"= T沖莊遞歸遍歷 =3.后序遞歸遍歷= T-先岸非遞歸遍歷= 電序三謁歸遍歷= ._,rhl歸遍歷= 層次道歷社按任意犍退出程序說正在退出程序7.出錯信息"亠請輸入一棵二叉樹；a,d<a9-二輸入有誤按任意犍退岀程序六、設計總