【文章內(nèi)容簡介】 ........................................................17致 謝 ..............................................................................................................................18參考文 獻 ..............................................................................................................................18長春建筑學院《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計（論文） 1 第 1 章 緒 論引言： 樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中一樹和二叉樹最重要。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構(gòu)夠可以用樹來形象表示。樹在計算機領(lǐng)域中也得到了廣泛應用，如在編譯程序中，可以用樹來表示源程序的語法結(jié)構(gòu)。二叉樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，對它進行操作時總需要對每個數(shù)據(jù)逐一進行操作，這樣就存在一個操作順序問題，由此提出了二叉樹的遍歷操作問題，所謂遍歷二叉樹就是按某種順序訪問二叉樹中某個結(jié)點一次且僅一次的過程，這里。 設(shè)計目的。 、中序和后序遍歷的基本操作。 設(shè)計內(nèi)容 利用二叉樹特點和功能實現(xiàn)先序、中序和后序遍歷系統(tǒng)的實現(xiàn)，具體功能：輸入、輸出遍歷結(jié)果、先序遍歷、中序遍歷和后序遍歷，并能在屏幕上輸出操作前后的結(jié)果。 設(shè)計要求,并建模。 ,界面友好。 。長春建筑學院《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計（論文） 2 設(shè)計思想。 。另外還有層次遍歷，來充分實現(xiàn)本書對樹的遍歷。 ，采用邊查找邊刪除的方式。如果沒有查找到，則不對樹做任何的修改；如果查找到結(jié)點則刪除。 系統(tǒng)模塊劃分 。 ，逐個加入，逐個建立。 ，對數(shù)進行插入刪除。 ，包括將所有方法歸并在一起，還要建立查看界面一邊有系統(tǒng)的視覺效果。 主要功能模塊設(shè)計 程序主要設(shè)計了幾個功能：首先是創(chuàng)建二叉排序樹，完成后出現(xiàn)任務菜單，菜單中設(shè)計了八個模塊：樹狀輸出二叉樹，前序遍歷二叉樹，中序遍歷二叉樹，后序遍歷二叉樹，輸出葉子結(jié)點，輸出葉子結(jié)點個數(shù)，輸出二叉樹的深度，退出。長春建筑學院《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計（論文） 3 第 2 章 系統(tǒng)總體設(shè)計 基本理論（1）建立二叉樹的操作就是用遞歸算法以先序遍歷的次序從根結(jié)點開始建立一棵二叉樹。（2）利用棧的非遞歸算法對二叉樹進行遍歷，從二叉樹的根結(jié)點開始，自頂向下，同層自左往右訪問樹中的每個結(jié)點，此時，保存結(jié)點的順序和訪問的順序剛好一致。（3）用遞歸算法求出左右子樹的深度。需求分析 ：（1）輸入二叉樹的特殊先序序列，建立二叉樹。（2）實現(xiàn)二叉樹的層次遍歷和中序遍歷。（3）求二叉樹的深度。（4）將二叉樹中所有結(jié)點的左右子樹相互交換。（5）求二叉樹中葉子結(jié)點的數(shù)目。 概要設(shè)計CreatBinTree(amp。T):建立一棵二叉樹，Value(T,e)：查找值為 e 的二叉樹結(jié)點，并返回該結(jié)點的地址。BinTreeDepth(T)：返回二叉樹的深度，Parent(T,e)：查找二叉樹 T 中的值為 e 的結(jié)點的雙親，若沒有根結(jié)點，則操作失敗。PreOrderTraverse(T)：先序遍歷二叉樹，并輸出結(jié)點序列。InorderTraverse(T)：中序遍歷二叉樹，并輸出結(jié)點序列。PostOrderTraverse(T)：后序遍歷二叉樹，并輸出結(jié)點序列。 LevelOrderTraverse(T)：層次遍歷二叉樹，并輸出結(jié)點序列。說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。長春建筑學院《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計（論文） 4 第 3 章 詳細設(shè)計 建立二叉樹Void CreateBinTree(BinTreeamp。T) {//按先序次序輸入二叉樹中結(jié)點的值 //構(gòu)造二叉鏈表表示的二叉樹 T TelemType ch； Scanf(“%c”,amp。ch)。 If(i==’’) T=Null。 Else { T=(BinTree)malloc(sizeof(BinTNode))。 //生成根結(jié)點 Id(!=T) Exit(0)。 Tdata=ch。 CreateBinTree(Tlchild)。 //構(gòu)造左子樹 CreateBinTree(Trchild)。 //構(gòu)造右子樹 } Return。 } 二叉樹的層次遍歷和中序遍歷中序遍歷模塊（以中序為例來說明）遍歷（Traversal）是指沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問。訪問結(jié)點所做的操作依賴于具體的應用問題。二叉樹共有三個部分組成，即根結(jié)點，根結(jié)點的左子樹，根結(jié)點的右子樹。限定以從左至右方式共有三種遍歷方式，即前序遍歷，中序遍歷，后序遍歷。中序遍歷的原則：若被遍歷的二叉樹為非空，則依次執(zhí)行如下操作：長春建筑學院《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計（論文） 5 include // malloc()等include // 標準輸入輸出頭文件，包括 EOF(=^Z 或 F6)，NULL 等 include // atoi()，exit()include // 數(shù)學函數(shù)頭文件，包括 floor()，ceil()，abs()等 define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣 typedef struct BiTNode { int data。 // 結(jié)點的值 BiTNode *lchild,*rchild。 // 左右孩子指針}BiTNode,*BiTree。 int Nil=0。 // 設(shè)整型以 0 為空 void visit(int e) { printf(%d ,e)。 // 以整型格式輸出 }void InitBiTree(BiTree amp。T) { // 操作結(jié)果：構(gòu)造空二叉樹 T T=NULL。} void CreateBiTree(BiTree amp。T) { // 算法 ：按先序次序輸入二叉樹中結(jié)點的值(可為字符型或整型，在主程中定義)， // 構(gòu)造二叉鏈表表示的二叉樹 T。變量 Nil 表示空(子)樹。修改int number。scanf(%d,amp。number)。 // 輸入結(jié)點的值 if(number==Nil) // 結(jié)點的值為空 T=NULL。else // 結(jié)點的值不為空 { T=(BiTree)malloc(sizeof(BiTNode))。// 生成根結(jié)點 if(!T) exit(OVERFLOW)。 Tdata=number。 // 將值賦給 T 所指結(jié)點 CreateBiTree(Tlchild)。 // 遞歸構(gòu)造左子樹 長春