基于二叉樹遍歷系統(tǒng)設計與實現(xiàn)課程設計論文

1、長春建筑學院?數(shù)據(jù)結構?課程設計論文基于二叉樹遍歷系統(tǒng)設計與實現(xiàn)基于二叉樹遍歷系統(tǒng)設計與實現(xiàn)Binary tree traversal System Design and Implementation年 級: 學 號: 姓 名: 專 業(yè): 指導老師: 二零一三年十二月摘 要 針對現(xiàn)實世界中許多關系復雜的數(shù)據(jù)，如人類社會的家譜，各種社會組織機構,博弈交通等復雜事物或過程以及客觀世界中廣泛存在的具有分支關系或層次特性的對象如操作系統(tǒng)的文件構成、人工智能和算法分析的模型表示以及數(shù)據(jù)庫系統(tǒng)的信息組織形式等，用線性結構難以把其中的邏輯關系表達出來，必須借助于數(shù)和圖這樣的非線性結構，因此在以模擬客觀世界問

2、題，解決客觀世界問題為主要任務的計算機領域中樹型結構是信息的一種重要組織形式，樹有著廣泛應用。在樹型結構的應用中又以二叉樹最為常用。二叉樹是一種非常重要的非線性結構，所描述的數(shù)據(jù)有明顯的層次關系，其中的每個元素只有一個前驅，二叉樹是最為常用的數(shù)據(jù)結構，它的實際應用非常廣泛，二叉樹的遍歷方式有三種，前序遍歷，中序遍歷，后序遍歷，先序遍歷的順序為：NLR 先根結點，然后左子樹，右子樹；中序遍歷順序為；LNR 先左子樹，然后根結點，右子樹；后序遍歷順序為：LRN 先左子樹，然后右子樹，根結點。由前序和中序遍歷，有中序和后序遍歷序列可以唯一確定一棵二叉樹。對于給幾個數(shù)據(jù)的排序或在的幾個數(shù)據(jù)中進行查找，

3、二叉樹均能提供一種十分有效的方法，比方在查找問題上，任何借助于比擬法查找長度為的一個序表的算法，都可以表示成一株二叉樹。反之，任何二叉樹都對應一個查找有序表的有效方法根據(jù)樹的數(shù)學理論，對于算法分析的某些最有啟發(fā)性的應用，是與給出用于計算各種類型中不同樹的數(shù)目的公式有關的。本文對二叉樹以及二叉樹的各種功能做介紹以及寫出一些根本的程序，讓讀者對二叉樹的理解有更好的效果。關鍵詞：二叉樹； 左子樹； 右子樹AbstractIn many real world of complex data, such as the human society family, social organization,

4、widespread game traffic complex thing or process and the objective world with a branch or level characteristics of the object. If the operating system file analysis, artificial intelligence and algorithm model representation and database information system the form of organization, with a linear str

5、ucture to express the logic relationship among them, must depend on the number and the diagram of such nonlinear structure, so in order to simulate the objective world, solve problems as the main task of the computer field in the tree structure is an important organization form of information, the t

6、ree has a broad application. In the application of tree structure in which the two fork tree is the most commonly used.Two binary tree is a kind of very important nonlinear structure, hiberarchy description of the data, where each element is only a precursor, two fork tree is the most commonly used

7、data structure, its application is very extensive, there are three kinds of two binary tree traversal, preorder traversal, in the traversal, postorder traversal, preorder traversal sequence: NLR to the root node, and then the left subtree, right subtree; in order traversal sequence; LNR before the l

8、eft sub tree, then the root node, the right subtree; after the traversal order: LRN first and then the left subtree, right subtree, root node. By preorder traversal and traversal, with the order and post order traversal sequence can be uniquely identified a two binary tree.For several data sorting o

9、r searching in several data known, two fork tree can provide a very effective method, such as search problems, any by the comparison method to find the length of a sequential algorithm of Table IV, can be expressed as a two fork tree. Conversely, any two fork tree corresponds to an effective method

10、to find the ordered list according to the mathematical theory of tree, for some algorithm analysis of the application of heuristic, is given for the number and different types of tree calculation formula.Various functions of two binary tree and binary tree in this paper two introduces and write some

11、 of the basic procedures, to allow readers to understand the two fork tree has a better effect.Keywords:Two tree; the left subtree; right subtree目 錄摘 要 .IABSTRACT. 第 1 章 緒 論.11.1 設計目的.11.2 設計內容.11.3 設計要求.11.4 設計思想.21.5 系統(tǒng)模塊劃分.21.6 主要功能模塊設計.2第 2 章 系統(tǒng)總體設計.32.1 根本理論.32.2 概要設計.3第 3 章 詳細設計.43.1 建立二叉樹.43.

12、2 二叉樹的層次遍歷和中序遍歷.43.3 求二叉樹的深度.73.4 將二叉樹中所有結點的左右子樹相互交換.73.5 求二叉樹中葉子結點的數(shù)目.9第 4 章 流程分析圖.114.1 流程圖.114.2 主要功能模塊設計.114.3 模塊設計.124.4 函數(shù)主要調用關系圖.13第 5 章 系統(tǒng)測試.145.1 調試分析.145.2 實驗結果.15結 論.17致 謝.18參考文獻.18第 1 章 緒 論引言：引言： 樹型結構是一類重要的非線性數(shù)據(jù)結構，其中一樹和二叉樹最重要。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構夠可以用樹來形象表示。樹在計算機領域中也得到了廣泛應用，如在編

13、譯程序中，可以用樹來表示源程序的語法結構。二叉樹是一種非線性數(shù)據(jù)結構，對它進行操作時總需要對每個數(shù)據(jù)逐一進行操作，這樣就存在一個操作順序問題，由此提出了二叉樹的遍歷操作問題，所謂遍歷二叉樹就是按某種順序訪問二叉樹中某個結點一次且僅一次的過程，這里的訪問可以是輸出.比擬.更新.查看元素內容等各種操作。1.1 設計目的1.掌握二叉樹結點結構的建立。 2.掌握先序、中序和后序遍歷的根本操作。1.2 設計內容 利用二叉樹特點和功能實現(xiàn)先序、中序和后序遍歷系統(tǒng)的實現(xiàn)，具體功能：輸入、輸出遍歷結果、先序遍歷、中序遍歷和后序遍歷，并能在屏幕上輸出操作前后的結果。1.3 設計要求1.寫出系統(tǒng)需求分析,并建模。

14、 2.編程實現(xiàn),界面友好。 3.輸出操作前后的結果。4.提供測試報告。1.41.4 設計思想設計思想1.建立二叉樹采用一個一個輸入的方式。 2.對二叉樹進中序遍歷采用遞歸函數(shù)和非遞歸函數(shù)分別實現(xiàn)多種遍歷的方式。另外還有層次遍歷，來充分實現(xiàn)本書對樹的遍歷。 3.刪除結點函數(shù)，采用邊查找邊刪除的方式。如果沒有查找到，那么不對樹做任何的修改；如果查找到結點那么刪除。1.51.5 系統(tǒng)模塊劃分系統(tǒng)模塊劃分 1.二叉樹是一種動態(tài)樹表。 2.開辟一個空間建立一個節(jié)點，逐個參加，逐個建立。 3.利用查找函數(shù)，對數(shù)進行插入刪除。 4.利用書中所學知識進行各種遍歷，包括將所有方法歸并在一起，還要建立查看界面一邊

15、有系統(tǒng)的視覺效果。1.61.6 主要功能模塊設計主要功能模塊設計 程序主要設計了幾個功能：首先是創(chuàng)立二叉排序樹，完成后出現(xiàn)任務菜單，菜單中設計了八個模塊：樹狀輸出二叉樹，前序遍歷二叉樹，中序遍歷二叉樹，后序遍歷二叉樹，輸出葉子結點，輸出葉子結點個數(shù)，輸出二叉樹的深度，退出。第 2 章 系統(tǒng)總體設計2.1 根本理論1建立二叉樹的操作就是用遞歸算法以先序遍歷的次序從根結點開始建立一棵二叉樹。（2）利用棧的非遞歸算法對二叉樹進行遍歷，從二叉樹的根結點開始，自頂向下，同層自左往右訪問樹中的每個結點，此時，保存結點的順序和訪問的順序剛好一致。（3）用遞歸算法求出左右子樹的深度。需求分析 ：1輸入二叉樹的

16、特殊先序序列，建立二叉樹。2實現(xiàn)二叉樹的層次遍歷和中序遍歷。3求二叉樹的深度。4將二叉樹中所有結點的左右子樹相互交換。5求二叉樹中葉子結點的數(shù)目。2.2 概要設計CreatBinTree(&T):建立一棵二叉樹，Value(T,e)：查找值為 e 的二叉樹結點，并返回該結點的地址。BinTreeDepth(T)：返回二叉樹的深度，Parent(T,e)：查找二叉樹 T 中的值為 e 的結點的雙親，假設沒有根結點，那么操作失敗。PreOrderTraverse(T)：先序遍歷二叉樹，并輸出結點序列。InorderTraverse(T)：中序遍歷二叉樹，并輸出結點序列。PostOrderT

17、raverse(T)：后序遍歷二叉樹，并輸出結點序列。 LevelOrderTraverse(T)：層次遍歷二叉樹，并輸出結點序列。說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次(調用)關系。第 3 章 詳細設計Void CreateBinTree(BinTree&T) /按先序次序輸入二叉樹中結點的值 /構造二叉鏈表表示的二叉樹 T TelemType ch； Scanf(“%c,&ch); If(i=) T=Null; Else T=(BinTree)malloc(sizeof(BinTNode); /生成根結點 Id(!=T) Exit(0

18、); T-data=ch; CreateBinTree(T-lchild); /構造左子樹 CreateBinTree(T-rchild); /構造右子樹 Return; 3.2 二叉樹的層次遍歷和中序遍歷中序遍歷模塊以中序為例來說明遍歷Traversal是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴于具體的應用問題。二叉樹共有三個局部組成，即根結點，根結點的左子樹，根結點的右子樹。限定以從左至右方式共有三種遍歷方式，即前序遍歷，中序遍歷，后序遍歷。中序遍歷的原那么：假設被遍歷的二叉樹為非空，那么依次執(zhí)行如下操作：#include / malloc()等

19、#include / 標準輸入輸出頭文件，包括 EOF(=Z 或 F6)，NULL 等 #include / atoi()，exit()#include / 數(shù)學函數(shù)頭文件，包括 floor()，ceil()，abs()等 #define ClearBiTree DestroyBiTree / 清空二叉樹和銷毀二叉樹的操作一樣 typedef struct BiTNode int data; / 結點的值 BiTNode *lchild,*rchild; / 左右孩子指針BiTNode,*BiTree; int Nil=0; / 設整型以 0 為空 void visit(int e) prin

20、tf(%d ,e); / 以整型格式輸出 void InitBiTree(BiTree &T) / 操作結果：構造空二叉樹 T T=NULL; void CreateBiTree(BiTree &T) / 算法 6.4：按先序次序輸入二叉樹中結點的值(可為字符型或整型，在主程中定義)， / 構造二叉鏈表表示的二叉樹 T。變量 Nil 表示空(子)樹。修改int number;scanf(%d,&number); / 輸入結點的值 if(number=Nil) / 結點的值為空 T=NULL;else / 結點的值不為空 T=(BiTree)malloc(sizeof(B

21、iTNode);/ 生成根結點 if(!T) exit(OVERFLOW); T-data=number; / 將值賦給 T 所指結點 CreateBiTree(T-lchild); / 遞歸構造左子樹 CreateBiTree(T-rchild); / 遞歸構造右子樹 void DestroyBiTree(BiTree &T) / 初始條件：二叉樹 T 存在。操作結果：銷毀二叉樹 T if(T) / 非空樹 DestroyBiTree(T-lchild); / 遞歸銷毀左子樹，如無左子樹，那么不執(zhí)行任何操作 DestroyBiTree(T-rchild); / 遞歸銷毀右子樹，如無右

22、子樹，那么不執(zhí)行任何操作 free(T); / 釋放根結點T=NULL; / 空指針賦 0 void PreOrderTraverse(BiTree T,void(*Visit)(int) / 初始條件：二叉樹 T 存在，Visit 是對結點操作的應用函數(shù)。修改算 / 操作結果：先序遞歸遍歷 T，對每個結點調用函數(shù) Visit 一次且僅一次 if(T) / T 不空 Visit(T-data); / 先訪問根結點 PreOrderTraverse(T-lchild,Visit); / 再先序遍歷左子樹 PreOrderTraverse(T-rchild,Visit); / 最后先序遍歷右子樹

23、void InOrderTraverse(BiTree T,void(*Visit)(int) / 初始條件：二叉樹 T 存在，Visit 是對結點操作的應用函數(shù) / 操作結果：中序遞歸遍歷 T，對每個結點調用函數(shù) Visit 一次且僅一次 if(T) InOrderTraverse(T-lchild,Visit); / 先中序遍歷左子樹Visit(T-data); / 再訪問根結點 InOrderTraverse(T-rchild,Visit); / 最后中序遍歷右子樹 void PostOrderTraverse(BiTree T,void(*Visit)(int) / 初始條件：二叉樹

24、T 存在，Visit 是對結點操作的應用函數(shù) / 操作結果：后序遞歸遍歷 T，對每個結點調用函數(shù) Visit 一次且僅一次if(T) / T 不空 PostOrderTraverse(T-lchild,Visit); / 先后序遍歷左子樹 PostOrderTraverse(T-rchild,Visit); / 再后序遍歷右子樹 Visit(T-data); / 最后訪問根結點 void main() BiTree T; InitBiTree(T); / 初始化二叉樹 T printf(按先序次序輸入二叉樹中結點的值,輸入 0 表示節(jié)點為空， 輸入范例：1 2 0 0 3 0 0n); Cre

25、ateBiTree(T); / 建立二叉樹 T printf(先序遞歸遍歷二叉樹：n); PreOrderTraverse(T,visit); /先序遞歸遍歷二叉樹 T printf(n 中序遞歸遍歷二叉樹：n); InOrderTraverse(T,visit); /中序遞歸遍歷二叉樹 T printf(n 后序遞歸遍歷二叉樹：n); PostOrderTraverse(T,visit); /后序遞歸遍歷二叉樹 T 求二叉樹的深度樹的深度組成該樹各結點的最大層次Int BinTreeDepth(BinTree T) /初始條件：二叉樹存在 /操作結果：返回 T 的深度 Int i,j; if

26、 (!T) return 0; /i 為左子樹的深度 i=BinTreeDepth(BinTree T-lchild); /j 為右子樹的深度 J= BinTreeDepth(BinTree T-rchild); Return (ij)?(i+1):(j+1)3.4 將二叉樹中所有結點的左右子樹相互交換#include #include typedef struct binode int data; struct binode *lchild,*rchild; binode,*bitree; typedef struct bitree elem100; int top; stack; bitr

27、ee creat_bt()/按擴展前序建二叉樹 bitree t;int x; scanf(%d,&x); if (x=0) t=NULL; else t=(bitree)malloc(sizeof(binode); t-data=x; t-lchild=creat_bt(); t-rchild=creat_bt(); return t; void exchange(bitree t) /左、右子樹交換 bitree p; if(t!=NULL) p=t-lchild;t-lchild=t-rchild;t-rchild=p; exchange(t-lchild); exchange(

28、t-rchild); void inorder(bitree bt) /遞歸的中序遍歷 if (bt) inorder(bt-lchild); printf(% d,bt-data);inorder(bt-rchild); main() bitree root; printf(n); printf(建二叉樹，輸入元素：); root=creat_bt(); /*create tree of useing preorder*/ printf(交換前的中序序列是：); inorder(root); exchange(root); printf(n 交換后的中序序列是：); inorder(root

29、); printf(n); return; 3.5 求二叉樹中葉子結點的數(shù)目#include using namespace std; typedef struct TNode/二叉樹結構 char nodeValue;/結點的值 TNode* left;/左子樹 TNode* right;/右子樹 *BiTree; void CreateBiTree(BiTree &T)/中序遍歷方式創(chuàng)立二叉樹 ,輸入#代表該結點空 char nodeValue; cin nodeValue; if(nodeValue!=#)/結點非空 T=new TNode; T-nodeValue=nodeVa

30、lue; CreateBiTree(T-left); CreateBiTree(T-right); else T=NULL; int CountLeaf(BiTree T) static int LeafNum=0;/葉子初始數(shù)目為 0，使用靜態(tài)變量 if(T)/樹非空 if(T-left=NULL&T-right=NULL)/為葉子結點 LeafNum+;/葉子數(shù)目加 1 else/不為葉子結點 CountLeaf(T-left);/遞歸統(tǒng)計左子樹葉子數(shù)目 CountLeaf(T-right);/遞歸統(tǒng)計右子樹葉子數(shù)目 return LeafNum; 該模塊功能主要是給用戶提供清晰的

31、可操作界面，易于人機操作，并能很好的調用其他各模塊，使程序更加優(yōu)化，絲路更加清晰，結構更加明了，提高了程序的實用性。其算法如下： /用來測試的 main 函數(shù)，int main() BiTree T; int leafNum; cout請輸入中序遍歷的二叉樹序列(#號代表該結點為空)：如(ABC#DE#G#F#)endl; CreateBiTree(T); leafNum=CountLeaf(T); cout該二叉樹中葉子結點數(shù)為：leafNumendl; return 0; 第四章 流程分析圖4.1 二叉樹的生成過程二叉樹的生成，采用逐個建立的方式。如下圖： 圖圖 4-14-1 二叉樹建立二

32、叉樹建立4.2 主要功能模塊設計 程序主要設計了幾個功能：首先是創(chuàng)立二叉排序樹，完成后出現(xiàn)任務菜單，菜單中設計了八個模塊：樹狀輸出二叉樹，前序遍歷二叉樹，中序遍歷二叉樹，后序遍歷二叉樹，輸出葉子結點，輸出葉子結點個數(shù)，輸出二叉樹的深度，退出。主函數(shù)流程如下：初始化數(shù)組插入頭結點點空樹添加左子輸添加右孩數(shù)插入插入插入是是否否是是是是 圖圖 4-24-2 主函數(shù)流程圖主函數(shù)流程圖模塊設計模塊設計本程序包含三個模塊：主程序模塊、建立二叉樹模塊和工作區(qū)模塊。其調用關系如圖 4-3 所示。 主程序模塊建立二叉樹模塊工作區(qū)選擇模塊4-34-3 模塊調用示意圖模塊調用示意圖否否否否否是創(chuàng)立二叉排序樹Swit

33、ch()遞歸遍歷Switch(0)Exit(0)退出Switch()刪除結點Switch()default提示出錯非遞歸遍歷是是是是4.44.4 函數(shù)主要調用關系圖函數(shù)主要調用關系圖本系統(tǒng) 11 個子程序之間的主要調用關系如圖 4-4 所示。圖中數(shù)字是各函數(shù)的編號。10 mainwork()98765423111 main()4-44-4 系統(tǒng)函數(shù)調用關系圖系統(tǒng)函數(shù)調用關系圖第第 5 章章 系統(tǒng)測試系統(tǒng)測試5.1 調試分析 1在調試過程中出現(xiàn)了很屢次的程序錯誤，警告和不能運行。在很屢次的調試和重新改寫之后，才可以用。 2Visual C+確實是一門需要極其細心和耐心的課程，尤其在程序設計的過程中不可有一絲的馬虎大意，否那么將會花很大力氣去改正。3.調試過程中最常見的