數(shù)據(jù)結(jié)構(gòu)課程設計任務書

課程設計任務書一、 設計題目二叉樹的相關(guān)操作二、 主要內(nèi)容建立二叉樹，并對樹進行相關(guān)操作。三、 具體要求1） 利用完全二叉樹的性質(zhì)建立一棵二叉樹。（層數(shù)不小于4層）2） 統(tǒng)計樹葉子結(jié)點的個數(shù)。3） 求二叉樹的深度。4） 能夠輸出用前序，中序，后序?qū)Χ鏄溥M行遍歷的遍歷序列。四、 進度安排依照教學計劃，課程設計時間為：2周。3.5-3.6,資料查找、系統(tǒng)分析，概要設計。3.7-3.15系統(tǒng)詳細設計、功能設計算法實現(xiàn)、編程調(diào)試、檢查問答。3.19-3.26,歸納文檔資料，按要求填寫“課程設計說明書”上交課程設計材料。五、 完成后應上交的材料1、 課程設計說明書（所使用的數(shù)據(jù)結(jié)構(gòu)說明、程序流程圖、功能模塊圖、核心算法等）。2、 相關(guān)源程序文件。六、 總評成績指導教師 簽名日期 年—月—日系主任 審核日期 年—月—日目錄TOC\o"1-5"\h\z一緒論 3\o"CurrentDocument"二需求分析 3三總體設計 33.1各功能模塊設計 3\o"CurrentDocument"3.1.1定義二叉樹的結(jié)點類型 3\o"CurrentDocument"3.1.2主函數(shù) 3\o"CurrentDocument"3.1.3定義結(jié)點創(chuàng)建二叉樹 4\o"CurrentDocument"3.1.4計算樹的深度和葉子數(shù) 43.1.5前序遍歷 43.1.6中序遍歷 43.1.7后序遍歷 4\o"CurrentDocument"3.2流程圖 4四詳細設計 5五程序運行結(jié)果 8\o"CurrentDocument"六總結(jié) 8、緒論二叉樹是樹形結(jié)構(gòu)的一個重要的類型，二叉樹是n（n>=0）個結(jié)點的有限集，它或者是空集（n=0），或者由個根結(jié)點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。二叉樹的存儲結(jié)構(gòu)和算法比較簡單，特別適合計算機處理。即使一般形式的樹也可簡單的轉(zhuǎn)換為二叉樹。二叉樹的順序存儲結(jié)構(gòu)是把二叉樹的所有結(jié)點，按照一定的次序順序，存儲到一片連續(xù)的存儲單元中。遍歷二叉樹就是沿某有前序遍歷、中條搜索路徑周游二叉樹，對樹中每個結(jié)點訪問一次且僅訪問一次。在遍歷方案中主要序遍歷、后序遍歷?，F(xiàn)實中有許多應用到二叉樹的例子，所以我們要把理論與現(xiàn)實結(jié)合起來。在學習中主要掌握怎么求二叉樹的高度、葉子結(jié)點個數(shù)、總結(jié)點個數(shù)以及熟練三種遍歷的方法。二、 需求分析1） 利用完全二叉樹的性質(zhì)建立一棵二叉樹。（層數(shù)不小于4層）2） 統(tǒng)計樹葉子結(jié)點的個數(shù)。3） 求二叉樹的深度。4） 能夠輸出用前序，中序，后序?qū)Χ鏄溥M行遍歷的遍歷序列。三、 總體設計3.1各個功能模塊設計本程序采用了各種同的方法對同一個輸入進行排序，且每一個元素其本身亦是一個結(jié)構(gòu)體，又可以進行擴充，使其可以存儲其他的相關(guān)的信息。通過二叉樹的建立來實現(xiàn)二叉樹各種遍歷、葉子結(jié)點的個數(shù)、二叉樹的深度。3.1.1定義二叉樹的結(jié)點類型為創(chuàng)建二叉樹做準備3.1.2主函數(shù)創(chuàng)建數(shù)組儲存數(shù)據(jù)，順序輸出前序遍歷、中序遍歷、后序遍歷3.1.3定義結(jié)點創(chuàng)建二叉樹利用數(shù)組儲存后的數(shù)據(jù)，創(chuàng)建樹，從而完成建樹的功能3.1.4計算樹的深度和葉子數(shù)利用while循環(huán)函數(shù)，簡單明了地探索已經(jīng)建立的完全二叉樹的深度和統(tǒng)計樹的葉子數(shù)3.1.5前序遍歷利用遞歸算法的實現(xiàn)前序遍歷，首先訪問根結(jié)點然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。3.1.6中序遍歷利用遞歸算法來實現(xiàn)中序遍歷，首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷左子樹，再訪問根結(jié)點，最后遍歷右子樹。3.1.7后序遍歷利用遞歸算法來實現(xiàn)后序遍歷，首先遍歷左子樹，然后遍歷右子樹，最后遍歷訪問根結(jié)點，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后遍歷根結(jié)點。3.2流程圖由題目要求，畫出程序流程圖如下：1/\TOC\o"1-5"\h\z2 3/\ \4 5 6/\/\78910開始I崟義二叉樹的結(jié)點類型I建數(shù)組儲存數(shù)據(jù)I主函數(shù)輸出全部結(jié)果IM結(jié)點，創(chuàng)建完全二叉樹I計算樹的深度和葉子數(shù)前序遍歷]中序遍歷]后序遍歷I結(jié)束四、詳細設計#include<stdio.h>#include<stdlib.h>typedefstructnode〃定義二叉樹的結(jié)點類型{intElement;structnode*left,*right;}Node;Node*buildTree(int*arr,intlen);intcount(int*arr,intlen);intpreorder(Node*root);intmidorder(Node*root);intafterorder(Node*root);voidmain(){inti,n;inta[100];//創(chuàng)建數(shù)組儲存數(shù)據(jù)Node*root;printf("請輸入結(jié)點數(shù):");scanf("%d”,&n);printf(-請輸入總共%d個數(shù)據(jù)(請用空格間隔)：\n",n);for(i=0;i<n;i++){scanf("%d",&a[i]);}printf("\n");count(a,n);root=buildTree(a,n);printf("\n先序遍歷為：，preorder(root);printf("\n中序遍歷為：，midorder(root);printf("\n后序遍歷為：，afterorder(root);printf("\n");}Node*buildTree(int*arr,intlen)//定義結(jié)點{Node*Narr;inti;Narr=(Node*)malloc(sizeof(Node)*len);〃分配一個Node大小的空間返回指針轉(zhuǎn)換成Node類型for(i=0;i<len;i++){Narr[i].Element=arr[i];if(((i+1)*2-1)<len){Narr[i].left=&Narr[(i+1)*2-1];}elseNarr[i].left=NULL;if(((i+1)*2)<len){Narr[i].right=&Narr[(i+1)*2];}elseNarr[i].right=NULL;}returnNarr;}intcount(int*arr,intlen)//計算樹的深度和葉子數(shù){intdeep=0;intx=1;while(x<len){deep++;len-=x;x*=2;}printf("樹的深度為：%d,葉子數(shù)為：%d\n”,deep+1,x/2+len/2);return0;intpreorder(Node*root)//前序遍歷nlr{if(root==NULL)return1;else{printf("%d",root->Element);preorder(root->left);preorder(root->right);return0;}}intmidorder(Node*root)//中序遍歷lnr{if(root==NULL)return1;else{midorder(root->left);printf("%d",root->Element);midorder(root->right);return0;}}intafterorder(Node*root)//后序遍歷lrn{if(root==NULL)return1;else{afterorder(root->left);afterorder(root->right);printf("%d",root->Element);return0;}}五、程序運行結(jié)果

由"D:\我的文檔\Stud八關(guān)于二叉樹的相關(guān)操作\Debug\關(guān)于二一…亦入結(jié)點數(shù)：清茄茂結(jié)點藪云好請埼入總共10個數(shù)據(jù)（請用空格間隔）12345678910_oniiT的深度為：4188UJe力丸丸八歷歷歷an遍遍遍3eS先中后pp.：10個數(shù)據(jù)〔請用空格間隔09，葉子數(shù)為:S2 4 8 9 S 10 34 9 2 10 oniiT的深度為：4188UJe力丸丸八歷歷歷an遍遍遍3eS先中后pp.：10個數(shù)據(jù)〔請用空格間隔09，葉子數(shù)為:S2 4 8 9 S 10 34 9 2 10 S 1 69 4 105 2 6 7tocentisitie六、總結(jié)有一次的課程設計了，總結(jié)了之前的課程設計的教訓，所以這次的課程設計總算懂得如何將理論和實踐有機的結(jié)合在一起。這次做的二叉樹的相關(guān)操作，剛剛開