《二叉樹數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.doc》由會員分享，可在線閱讀，更多相關(guān)《二叉樹數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.doc（16頁珍藏版）》請在匯文網(wǎng)上搜索。

1、目 錄第一章 需求分析11.1課程設(shè)計題目11.2 課程設(shè)計任務(wù)及要求11.21 課程設(shè)計目的11.22 設(shè)計要求11.3課程設(shè)計思想21.4 軟件運行環(huán)境及開發(fā)工具2第二章概要設(shè)計32.1 數(shù)據(jù)結(jié)構(gòu)32.2 所用方法及其原理說明3第三章 詳細設(shè)計43.1 詳細設(shè)計方案43.2 模塊設(shè)計43.21 二叉樹定義43.22 樹狀顯示二叉樹設(shè)計73.22 主函數(shù)設(shè)計10第四章 調(diào)試和操作說明114.1 調(diào)試114.2 操作說明12第五章 總結(jié)與體會125.1 本文的主要工作125.2 存在問題125.3 心得體會12致 謝13參考文獻14第一章 需求分析1.1課程設(shè)計題目樹狀顯示二叉樹：編寫函數(shù)di

2、splaytree(二叉樹的根指針，數(shù)據(jù)值寬度，屏幕的寬度)輸出樹的直觀示意圖。輸出的二叉樹是垂直打印的，同層的節(jié)點在同一行上。問題描述 假設(shè)數(shù)據(jù)寬度datawidth=2,而屏幕寬度screenwidth為64=26,假設(shè)節(jié)點的輸出位置用（層號，須打印的空格數(shù)）來界定。第0層：根在（0，32）處輸出；第1層：因為根節(jié)點縮進了32個空格，所以下一層的偏移量（offset）為32/2=16=screenwidth/22。即第一層的兩個節(jié)點的位置為（1，32-offset）,(1,32+offset)即（1，16），（1，48）。第二層：第二層的偏移量offset為screenwidth/23。第

3、二層的四個節(jié)點的位置 分別是（2，16-offset），（2，16+offset），（2，48-offset），（2，48+offset）即（2，8），（2，24），（2，40），（2，56）。第i層：第i層的偏移量offset為screenwidth/2i+1。第i層的每個節(jié)點的位置是訪問第i-1層其雙親節(jié)點時確定的。假設(shè)其雙親的位置為（i-1，parentpos）。若其第i層的節(jié)點是其左孩子，那末左孩子的位置是（i，parentpos-offset），右孩子的位置是（i，parentpos+offset）。實現(xiàn)提示 利用二叉樹的層次遍歷算法實現(xiàn)。利用兩個隊列Q，QI。隊列Q中存放節(jié)點信息，

4、隊列QI中存相應(yīng)于隊列Q中的節(jié)點的位置信息，包括層號和需要打印節(jié)點值時需要打印的空格數(shù)。當節(jié)點被加入到Q時，相應(yīng)的打印信息被存到QI中。二叉樹本身采用二叉鏈表存儲。1.2 課程設(shè)計任務(wù)及要求1.21 課程設(shè)計目的據(jù)結(jié)構(gòu)是計算機專業(yè)的核心課程，是一門實踐性很強的課程。課程設(shè)計是加強學生實踐能力的一個強有力手段，要求學生掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫、類C語言的算法轉(zhuǎn)換成C（C+）程序并上機調(diào)試的基本方法，還要求學生在完成程序設(shè)計的同時能夠?qū)懗霰容^規(guī)范的設(shè)計報告。嚴格實施課程設(shè)計這一環(huán)節(jié)，對于學生基本程序設(shè)計素養(yǎng)的培養(yǎng)和軟件工作者工作作風的訓練，將起到顯著的促進作用。1.22 設(shè)計要求1、課程設(shè)計

5、題目每組一題，每個學生必須獨立完成；2、課程設(shè)計時間為2周；3、設(shè)計語言C（C+）不限；4、上機任務(wù)1）選擇合適的數(shù)據(jù)結(jié)構(gòu)，并定義數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)體；2）根據(jù)程序所要完成的基本要求，設(shè)計出完整的算法；3）設(shè)計出主程序（main函數(shù)），使其成為完整的程序。 6、上機時間：按照實驗室上機時間安排計劃執(zhí)行 7、無論在校外、校內(nèi)，都要嚴格遵守學校和所在單位的學習和勞動紀律、規(guī)章制度，學生有事離校必須請假。課程設(shè)計期間，無故缺席按曠課處理；缺席時間達四分之一以上者，其成績按不及格處理。1.3課程設(shè)計思想二叉樹是一種樹形結(jié)構(gòu)，它的特點是每個結(jié)點至多有兩棵子樹，即二叉樹中不存在度大于2的結(jié)點，并且二叉樹的子樹

6、有左右之分，其次序不能任意顛倒。本設(shè)計主要根據(jù)二叉樹的性質(zhì)原理為設(shè)計的主體思路，二叉樹的性質(zhì)如下:性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點（i=1）；性質(zhì)2：深度為K的二叉樹至多有2k-1個結(jié)點（K=1）；性質(zhì)3：如果一棵有n各結(jié)點的完全二叉樹的結(jié)點按層次編號，則對任一結(jié)點i(1=in,則結(jié)點無左孩子，否則其左孩子是結(jié)點2i；（2）若2i+1n,則結(jié)點i無右孩子，否則其右孩子為2i+1；另外，本設(shè)計利用二叉樹的廣度優(yōu)先搜索算法實現(xiàn)。利用兩個隊列Q，QI。隊列Q中存放節(jié)點信息，隊列QI中存相應(yīng)于隊列Q中的節(jié)點的位置信息，包括層號和需要打印節(jié)點值時需要打印的空格數(shù)。當節(jié)點被加入到Q時，相應(yīng)的

7、打印信息被存到QI中。二叉樹本身采用二叉鏈表存儲。本設(shè)計應(yīng)用了C語言中的類來自定義頭文件，將任務(wù)分成多個的模塊，增強了可讀性和簡單性，同時為日后的編寫，調(diào)試，維護提供了極大地方便。1.4 軟件運行環(huán)境及開發(fā)工具本設(shè)計用到的軟件是Microsoft Visual C+ 6.0程序開發(fā)軟件，Microsoft Visual C+ 6.0是20世紀90年代中期由美國微軟公司推出的一個強大的Windows應(yīng)用程序開發(fā)平臺，是“真正的程序員”首選的開發(fā)工具之一，也是有志于程序設(shè)計的程序員、大中專院校學生進入高級程序設(shè)計領(lǐng)域的首選軟件之一。Microsoft Visual C+ 6.0程序開發(fā)軟件提供了一

8、個可視化集成編程環(huán)境，能自動生成Windows應(yīng)用程序的共有部分，幫助程序設(shè)計人員直接切入實際功能部分的代碼編制主題，從而大大簡化了復雜的Windows應(yīng)用程序開發(fā)過程，極大的提高了程序設(shè)計的效率，其次， VC+功能強大，內(nèi)容浩瀚在該環(huán)境下用戶可以開發(fā)有關(guān)C和C+的各種應(yīng)用程序，應(yīng)用程序的開發(fā)包括建立、編輯、瀏覽、鏈接和調(diào)試等操作。第二章概要設(shè)計2.1 數(shù)據(jù)結(jié)構(gòu)樹狀顯示二叉樹是二叉樹的一種自然顯示方法，本設(shè)計結(jié)果將二叉樹形象的顯示在屏幕上，直觀易懂。因此本設(shè)計將對樹狀顯示二叉樹的設(shè)計步驟進行詳細說明。首先得構(gòu)造一個數(shù)組來存儲整個二叉樹的結(jié)點信息，建立兩個隊列Q和QI，隊列Q中存放節(jié)點信息，隊列

9、QI中存相應(yīng)于隊列Q中的節(jié)點的位置信息，包括層號和需要打印節(jié)點值時需要打印的空格數(shù)。當節(jié)點被加入到Q時，相應(yīng)的打印信息被存到QI中。然后通過插入排序算法來構(gòu)造一個二叉樹，并用二叉樹的層次遍歷來使二叉樹有順序的存入隊列Q，最后通過隊列QI使得二叉樹樹狀的顯示在屏幕上。該程序的主要流程圖如圖2-1所示。2.2 所用方法及其原理說明 本設(shè)計主要運用了樹的廣度優(yōu)先搜索和隊列的先進先出的特點，樹的廣度優(yōu)先搜索功能如下： 假設(shè)從圖中某頂點v出發(fā)，在訪問了v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有

10、已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。 隊列是一種先進先出的線性表，它只允許在表的一端進行插入，而在另一端刪除元素。在隊列中允許插入的一端叫隊尾，允許刪除的一端叫對頭。隊列的示意圖如下： 圖1 二叉樹示意圖第三章 詳細設(shè)計3.1 詳細設(shè)計方案本設(shè)計利用兩個隊列Q，QI，隊列Q中存放結(jié)點信息，隊列QI中存相應(yīng)于隊列Q中的節(jié)點的位置信息，包括層號和需要打印節(jié)點值時需要打印的空格數(shù)。當節(jié)點被加入到Q時，相應(yīng)的打印信息被存到QI中。用二叉樹（二叉樹本身采用二叉鏈表存儲）的層次遍歷算法實現(xiàn)了二叉

11、樹的樹狀顯示。本設(shè)計應(yīng)用了C語言中的類來自定義頭文件，將任務(wù)分成多個的模塊，增強了可讀性和簡單性，同時為日后的編寫，調(diào)試，維護提供了極大地方便。3.2 模塊設(shè)計本程序包括三部分，即二叉樹定義部分（MyHeap.h），樹狀顯示二叉樹的實現(xiàn)（MyHeap.cpp）部分以及最重要的主函數(shù)部分(main.cpp)。下面將對各模塊設(shè)計思想及設(shè)計方法進行詳細的說明。3.21 二叉樹定義需要顯示的二叉樹的示意圖如下： 圖2 樹狀二叉樹#include #include #include #define TElemType char#define OK 1#define ERROR 0#define OVER

12、FLOW -2#define TRUE 1#define FALSE 0typedef int Status ; #define MAXQSIZE 100 typedef struct BiNode int data; struct BiNode *lchild; struct BiNode *rchild;BiNode, *BiTree;typedef int ElemType;typedef struct ElemType *base; /*數(shù)組首地址*/ int front; /*頭指針,若隊列不空，指向隊列頭元素*/ int rear; /*尾指針,若隊列不空，指向隊列尾元素的下一個位

13、置*/SqQueue;typedef struct int level;int pos;bool enter;int spaceNum;DisplayInfo;Status insert(BiTree bt,int key)BiTree p,q,newNode; newNode=(BiTree)malloc(sizeof(BiNode);p=NULL;q=bt;while(q)p=q;if(keydata)q=q-lchild;else q=q-rchild;if(p)if(keydata)p-lchild=newNode;elsep-rchild=newNode;elsebt=newNode

14、;Status InitQueue(SqQueue *Q) Q-base=(ElemType *)malloc(MAXQSIZE*sizeof(ElemType); if (!Q-base) printf(分配空間失敗!); return OVERFLOW; Q-front=0; Q-rear=0; return OK;EnQueue(SqQueue *Q, ElemType e) /* 插入元素e為新的隊尾元素 */ if ( (Q-rear+1)%MAXQSIZE=Q-front ) printf(隊列滿了!); return ERROR; Q-baseQ-rear=e; Q-rear=(Q-rear+1)%MAXQSIZE;DeQueue(SqQueue *Q, ElemType *e) /* 刪除隊頭元素，并由e返回其值 */ if (Q-front=Q-rear) r