【正文】 以及數(shù)據(jù)庫系統(tǒng)的信息組織形式等，用線性結構難以把其中的邏輯關系表達出來，必須借助于數(shù)和圖這樣的非線性結構，因此在以模擬客觀世界問題，解決客觀世界問題為主要任務的計算機領域中樹型結構是信息的一種重要組織形式，樹有著廣泛應用。 in order traversal sequence。 設計目的 二叉樹結點結構 的建立。 采用遞歸函數(shù)和非遞歸函數(shù)分別實現(xiàn)多種遍歷的方式。 主要功能模塊設計 程序 主要設計了幾個功能：首先是創(chuàng)建二叉排序樹，完成后出現(xiàn)任務菜單，菜單中設計了八個模塊：樹狀輸出二叉樹，前序遍歷二叉樹，中序遍歷二叉樹，后序遍歷二叉樹，輸出葉子結點，輸出葉子結點個數(shù)，輸出二叉樹的深度，退出。 （ 5）求二叉樹中葉子結點的數(shù)目。說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次 (調用 )關系。 CreateBinTree(Tlchild)。 // 結點的值 BiTNode *lchild,*rchild。變量 Nil 表示空 (子 )樹。 // 將值賦給 T所指結點 CreateBiTree(Tlchild)。 // 空指針賦 0 } } void PreOrderTraverse(BiTree T,void(*Visit)(int)) { // 初始條件：二叉樹 T 存在， Visit 是對結點操作的應用函數(shù)。 // 先后序遍歷左子樹 PostOrderTraverse(Trchild,Visit)。 //先序遞歸遍歷二叉樹 T printf(\n 中序遞歸遍歷二叉樹： \n)。 Return (ij)?(i+1):(j+1)} 將二叉樹中所有結點的左右子樹相互交換 include include typedef struct binode{ int data。 scanf(%d,amp。 } void exchange(bitree t) //左、右子樹交換 {bitree p。 inorder(btrchild)。 printf(\n交換后的中序序列是： )。//右子樹 }*BiTree。 CreateBiTree(Tleft)。//遞歸統(tǒng)計左子樹 葉子數(shù)目 CountLeaf(Tright)。 cout該二叉樹中葉子結點數(shù)為： leafNumendl。 44 系統(tǒng)函數(shù)調用關系圖 10 mainwork() 9 8 7 6 5 4 2 3 1 11 main() 長春建筑學院《數(shù)據(jù)結構》課程設計 （論文） 14 第 5 章 系統(tǒng)測試 調試分析 1．在調試過程中出現(xiàn)了很多次的程序錯誤，警告和不能運行。 實驗結果 先序、中序遍歷： 長春建筑學院《數(shù)據(jù)結構》課程設計 （論文） 15 后序遍歷、輸出葉子結點： 輸出葉子結點個數(shù)、二叉樹深度： 長春建筑學院《數(shù)據(jù)結構》課程設計 （論文） 16 結果分析： 實驗 實現(xiàn)了二叉樹的三種遍歷算法，想要改進的話可以在擴充其功能上下手，例如實現(xiàn)更多遍歷算法，建立的時候提示更人性化，對輸入的數(shù)據(jù)進行有效性驗證等等。 致 謝 通過本次課程設計，使我對數(shù)據(jù)結構這門課的認識更進一步，數(shù)據(jù)結構作為計算機專業(yè)的一門必修 課，對如何編寫好的算法進行了比較深入的闡述，為我們寫出正確的，強壯的代碼奠定了基礎。反之，任何二叉樹都對應一個查找有序表的有效方法根據(jù)樹的數(shù)學理論，對于算法分析的某些最有啟發(fā)性的應用，是與給出用于計算各種類型中不同樹的數(shù)目的公式有關的。所以只要根據(jù)本程序的說明操作即可。 是 是 是 是 主程序模塊 建立二叉樹模塊 工作區(qū)選擇模塊 否 否 否 否 否 是 創(chuàng)建二叉排序樹 Switch() 遞歸遍歷 Switch(0) Exit(0)退出 Switch() 刪除結點 Switch() default 提示出錯 非遞歸遍歷 是 是 是 是 長春建筑學院《數(shù)據(jù)結構》課程設計 （論文） 13 43 模塊調用示意圖 函數(shù)主要調用關系圖 本系統(tǒng) 11 個子程序之間的主要調用關系如圖 44 所示。 CreateBiTree(T)。Tright==NULL)//為葉子結點 LeafNum++。)//結點非空 { T=new TNode。//結點的值 TNode* left。 inorder(root)。 } } void inorder(bitree bt) //遞歸的中序遍歷 { if (bt){ inorder(btlchild)。 trchild=creat_bt()。 bitree creat_bt(){//按擴展前序建二叉樹 bitree t。 //i 為左子樹的深度 i=BinTreeDepth(BinTree Tlchild)。 // 建立二叉樹 T printf(先序遞歸遍歷二叉樹： \n)。 // 再訪問根結點 InOrderTraverse(Trchild,Visit)。 // 遞歸銷毀右子樹，如無右子樹，則不執(zhí) 行任何操作 free(T)。// 生成根結點 if(!T) exit(OVERFLOW)。 } void CreateBiTree(BiTree amp。限定以從左至右方式共有三種遍歷方式，即前序遍歷，中序遍歷，后序遍歷。 //生成根結點 Id(!=T) Exit(0)。 PostOrderTraverse(T)：后序遍歷二叉樹，并輸出結點序列。 （ 3）求二叉樹的深度。 ，對數(shù)進行插入刪除 。 。樹在計算機領域中也得到了廣泛應用，如在編譯程序中，可以用樹來表示源程序的語法結構。 本文對二叉樹以及二叉樹的各種功能做介紹以及寫出一些基本的程序，讓讀者對二叉樹的理解有更好的效果。在樹型結構的應用中又以二叉樹最為常用。 LNR before the left sub tree, then the root node, the right subtree。 、中序和后序遍歷的基本操作。另外還有層次遍歷，來充分實現(xiàn)本書對樹的遍歷。 長春建筑學院《數(shù)據(jù)結構》課程設計 （論文） 3 第 2 章 系統(tǒng)總體設計 基本理論 （ 1）建立二叉樹的操作就是用遞歸算法以先序遍歷的次序從根結點開始建立一棵二叉樹。 概要設計 CreatBinTree(amp。 長春建筑學院《數(shù)據(jù)結構》課程設計 （論文） 4 第 3 章 詳細設計 Void CreateBinTree(BinTreeamp。 //構造左子樹 CreateBinTree(Trchild)。 // 左右孩子指針 }BiTNode,*BiTree。修改 int numbe