數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---判別給定的二叉樹是否為二叉排序樹

1、<p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p><b>　　目錄</b></p><p><b>　　1 需求分析3</b></p><p><b>　　2 概要設(shè)計(jì)4</b></p><p>　　2.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說明4<

2、;/p><p>　　2.2程序功能圖4</p><p>　　2.3算法流程圖5</p><p><b>　　3 詳細(xì)設(shè)計(jì)7</b></p><p><b>　　3.1程序分析7</b></p><p>　　3.2程序源代碼7</p><p>&l

3、t;b>　　4 調(diào)試分析9</b></p><p><b>　　5 課程總結(jié)11</b></p><p><b>　　6參考文獻(xiàn)12</b></p><p><b>　　1 需求分析</b></p><p>　　圖1-1 二叉樹</p>

4、<p>　　以圖1-1所示的二叉樹為例設(shè)計(jì)，建立一個(gè)以二叉鏈表方式存儲(chǔ)的二叉樹，輸入結(jié)點(diǎn)信息時(shí)按照完全二叉樹的結(jié)點(diǎn)順序輸入（1為虛結(jié)點(diǎn)，0為輸入結(jié)束）。由于一棵二叉排序樹中序遍歷后的序列是遞增有序的，因此可利用中序遍歷一棵二叉樹后的序列是否遞增有序來判斷是否為二叉排序樹。</p><p>　　如圖，二叉樹的結(jié)點(diǎn)輸入順序?yàn)?7 80 90 50 1 68 88 1 1 34 56 0 （1為虛結(jié)點(diǎn)，0為

5、輸入結(jié)束），中序遍歷之后的順序?yàn)?0 80 77 34 68 56 90 88 ，由于中序遍歷之后的序列不是遞增有序的，因此可判斷出此二叉樹不是二叉排序樹。</p><p><b>　　2 概要設(shè)計(jì)</b></p><p>　　2.1 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說明 </p><p>　　typedef struct node{</p>&

6、lt;p>　　int data; //數(shù)據(jù)域</p><p>　　node *lchild,*rchild; //左孩子指針，右孩子指針</p><p>　　}Bitree; //結(jié)點(diǎn)的結(jié)構(gòu)體定義</p><p><b>　　2.2程序功能圖</b></p><p>　　圖2-1 程

7、序功能圖</p><p><b>　　2.3算法流程圖</b></p><p>　　選取部分核心流程圖如下：</p><p>　　圖2-2 主要流程圖</p><p>　　圖2-3 建立二叉樹</p><p><b>　　3 詳細(xì)設(shè)計(jì)</b></p><p

8、><b>　　3.1程序分析</b></p><p>　　建立一個(gè)以二叉鏈表方式存儲(chǔ)的二叉樹，建立二叉樹時(shí)，按照完全二叉樹的結(jié)點(diǎn)順序輸入，1表示虛結(jié)點(diǎn)，0表示輸入結(jié)束。若不是虛結(jié)點(diǎn)時(shí)，則建立一個(gè)新結(jié)點(diǎn)，并且將其作為左孩子或右孩子結(jié)點(diǎn)連接到它的父結(jié)點(diǎn)上（第一個(gè)結(jié)點(diǎn)無父結(jié)點(diǎn)）；若是虛結(jié)點(diǎn)，則將空結(jié)點(diǎn)（NULL）作為左孩子或右孩子結(jié)點(diǎn)連接到它的父節(jié)點(diǎn)上。</p><p&g

9、t;　　判定二叉樹時(shí)，中序遍歷整棵二叉樹，訪問根結(jié)點(diǎn)時(shí)將根結(jié)點(diǎn)信息存入一個(gè)數(shù)組中，以用來比較中序遍歷后序列是否為空。比較數(shù)組元素時(shí)，從下標(biāo)為0的數(shù)組元素開始比較，先將下標(biāo)為i=0的a[i]與下標(biāo)為1的a[i+1]比較，如果a[i]>a[i+1]，則結(jié)束比較，即該二叉樹不是二叉排序樹，否則繼續(xù)比較，直至比較完整個(gè)數(shù)組元素。</p><p><b>　　3.2程序源代碼</b></p

10、><p>　　#include "stdafx.h" //編寫的任何.cpp文件都必須首先包含stdafx.h</p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#define max 10</p>

11、<p>　　typedef struct node{</p><p>　　int data; //數(shù)據(jù)域</p><p>　　node *lchild,*rchild; //左孩子指針，右孩子指針</p><p>　　}Bitree; //結(jié)點(diǎn)的結(jié)構(gòu)體定義</p><p>　　B

12、itree *B[max];</p><p>　　int temp=0;</p><p>　　int Btree[max];</p><p>　　Bitree *Creatree(){ //建立二叉樹</p><p>　　Bitree *T,*S;</p><p><b>　　int ch;</b

13、></p><p>　　int front,rear,sign;</p><p>　　sign=0; //結(jié)點(diǎn)的序號(hào)從0開始編號(hào)（按照完全二叉樹的順序標(biāo)記）</p><p>　　front=0; //雙親結(jié)點(diǎn)下標(biāo)初值</p><p>　　rear=-1; //自身結(jié)點(diǎn)下標(biāo)初值</p><p>

14、;　　T=NULL; //初始化樹T</p><p>　　printf("建立二叉樹(1表示虛結(jié)點(diǎn),0表示輸入結(jié)束):\n");</p><p>　　scanf("%d",&ch); //按完全二叉樹的順序輸入結(jié)點(diǎn)</p><p>　　while(ch!=0)</p><p><

15、b>　　{</b></p><p>　　if(ch!=1) //輸入結(jié)點(diǎn)不是虛結(jié)點(diǎn)</p><p><b>　　{ </b></p><p>　　S=(Bitree *)malloc(sizeof(Bitree)); //創(chuàng)建新結(jié)點(diǎn)S</p><p>　　S->data=ch;

16、 //將輸入的數(shù)據(jù)保存到S中</p><p>　　S->lchild=S->rchild=NULL; //將S的左右子樹為空</p><p>　　rear++; //結(jié)點(diǎn)下標(biāo)加1</p><p>　　B[rear]=S; //將S保存到數(shù)組B中，即從下標(biāo)為0開始存儲(chǔ)</p><p>　　if(rear

17、==front) //雙親結(jié)點(diǎn)下標(biāo)與本身下標(biāo)相同時(shí)，即無雙親結(jié)點(diǎn)（只有第一個(gè)結(jié)點(diǎn)會(huì)產(chǎn)生這種情況）</p><p><b>　　{ </b></p><p><b>　　T=S;</b></p><p>　　sign++; //結(jié)點(diǎn)的序號(hào)加1</p><p><b>　　}</b&

18、gt;</p><p>　　else //尋找雙親結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　if(sign%2==1) </p><p>　　B[front]->lchild=S; //S作為左孩子 </p><p>　　if(sign%2==0)&

19、lt;/p><p><b>　　{</b></p><p>　　B[front]->rchild=S;//S作為右孩子</p><p>　　front++;//下標(biāo)加1，即尋找下一個(gè)雙親結(jié)點(diǎn)</p><p><b>　　}</b></p><p>　　sign++;//結(jié)

20、點(diǎn)序號(hào)加1</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else{ //輸入結(jié)點(diǎn)為虛結(jié)點(diǎn)</p><p>　　if(sign%2==0) //為右子樹時(shí)</p><p>　　{front++;} //

21、雙親結(jié)點(diǎn)加1 即下一個(gè)雙親結(jié)點(diǎn)</p><p>　　sign++; //結(jié)點(diǎn)序號(hào)加1</p><p><b>　　}</b></p><p>　　scanf("%d",&ch);</p><p><b>　　}</b></p><p>&l

22、t;b>　　return T;</b></p><p><b>　　}</b></p><p>　　void Inorder(Bitree *T) //中序遍歷二叉樹T，并將每個(gè)結(jié)點(diǎn)數(shù)據(jù)存入數(shù)組中</p><p><b>　　{ </b></p><p>　　if(T!=

23、NULL) //如果樹不為空</p><p><b>　　{ </b></p><p>　　Inorder(T->lchild);</p><p>　　printf("%d\t",T->data);</p><p>　　Btree[temp]=T->data;<

24、/p><p><b>　　temp++;</b></p><p>　　Inorder(T->rchild);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int Judgesort_bitree(

25、int Btree[]) //判斷中序遍歷后的二叉樹是否是二叉排序樹</p><p><b>　　{ </b></p><p>　　int i,sign=1;</p><p>　　for(i=0;i<temp-1;i++) //用for循環(huán)語句 看二叉樹是否有序遞增</p><p><b>　　{

26、 </b></p><p>　　if(Btree[i]>Btree[i+1]) //不是有序遞增的</p><p><b>　　{ </b></p><p><b>　　sign=0;</b></p><p><b>　　break;</b><

27、/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return sign; </p><p><b>　　}</b></p><p>　　void Judgeout(int a)//判斷輸出 將sign賦給a

28、</p><p><b>　　{ </b></p><p><b>　　if(a==1)</b></p><p>　　printf("給定二叉樹是二叉排序樹!\n");</p><p><b>　　if(a==0)</b></p><

29、p>　　printf("給定二叉樹不是二叉排序樹!\n");</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　Bitree *T;</p><p>　　T

30、=Creatree(); //建立二叉樹</p><p>　　printf("中序遍歷:\n");</p><p>　　Inorder(T); //中序遍歷二叉樹</p><p>　　printf("\n");</p><p>　　Judgeout(Judgesort_bitree(Bt

31、ree)); //判斷是否為排序二叉樹</p><p><b>　　}</b></p><p><b>　　4 調(diào)試分析</b></p><p>　　實(shí)現(xiàn)了設(shè)計(jì)的所有要求，選取部分運(yùn)行示意圖。</p><p>　　圖4-1 給定二叉樹是二叉排序樹</p><p>　　圖4-

32、2 給定二叉樹不是二叉排序樹</p><p><b>　　結(jié)果分析：</b></p><p>　　成功的編譯了代碼，實(shí)驗(yàn)結(jié)果令人滿意。先說下判斷二叉樹數(shù)否為排序二叉樹的時(shí)間復(fù)雜度。二叉樹以二叉鏈表存儲(chǔ)，在建立二叉樹，中序遍歷二叉樹和判別時(shí)的時(shí)間復(fù)雜度都為O(n)。再說下編程遇到的問題，編程的關(guān)鍵是要建立一棵二叉樹和判別是否為排序二叉樹。其中判斷時(shí)，用到了遞歸的思想。

33、調(diào)試時(shí)也遇到了一些問題，由于對(duì)一些頭文件的不熟悉，缺少，導(dǎo)致程序無法運(yùn)行等小錯(cuò)誤通過查閱一些資料得到了解決。再有就是由于程序涉及到指針，因此有時(shí)指針隨機(jī)訪問到系統(tǒng)隱藏空間時(shí)會(huì)出現(xiàn)異常終端，通過改進(jìn)，異常出現(xiàn)的幾率大大降低，可認(rèn)為程序能近似完美運(yùn)行。最后說下算法的優(yōu)缺點(diǎn)，優(yōu)點(diǎn)是：由于使用二叉鏈表存儲(chǔ)，結(jié)構(gòu)簡(jiǎn)單，可以方便的構(gòu)造任何形狀的二叉樹，并可以方便的實(shí)現(xiàn)二叉樹的大多數(shù)操作。缺點(diǎn)是：查找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)操作實(shí)現(xiàn)起來比較麻煩。而且存儲(chǔ)效

34、率不高，進(jìn)一步優(yōu)化的話，可以逐條歸類存儲(chǔ)。算法改進(jìn)的話，可以調(diào)整下操作界面，使人機(jī)交流更簡(jiǎn)單，方便用戶操作。</p><p><b>　　5 課程總結(jié)</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)終于結(jié)束，真的很開心。經(jīng)過一個(gè)學(xué)期的學(xué)習(xí)，我覺得課設(shè)是對(duì)于我們數(shù)據(jù)結(jié)構(gòu)掌握程度的測(cè)驗(yàn)與評(píng)估。這兩周的課設(shè)，從開始的確定命題，到搜集資料，到初步編程，到修改代碼，到最終完成代

35、碼，這是一個(gè)學(xué)習(xí)的過程，一個(gè)升華的過程。我想課設(shè)的意義也是在于此吧。</p><p>　　這個(gè)程序由于使用二叉鏈表存儲(chǔ)，結(jié)構(gòu)簡(jiǎn)單，可以方便的構(gòu)造任何形狀的二叉樹，并可以方便的實(shí)現(xiàn)二叉樹的大多數(shù)操作。但是他也存在不足，查找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)操作實(shí)現(xiàn)起來比較麻煩。而且存儲(chǔ)效率不高，進(jìn)一步優(yōu)化的話，可以逐條歸類存儲(chǔ)。調(diào)試時(shí)也遇到了一些問題，由于對(duì)一些頭文件的不熟悉，缺少，導(dǎo)致程序無法運(yùn)行等小錯(cuò)誤通過查閱一些資料得到了解

36、決。再有就是由于程序涉及到指針，因此有時(shí)指針隨機(jī)訪問到系統(tǒng)隱藏空間時(shí)會(huì)出現(xiàn)異常終端，通過改進(jìn)，異常出現(xiàn)的幾率大大降低，可認(rèn)為程序能近似完美運(yùn)行。</p><p>　　雖然剛開始很困難，但是只要你愿意做，就一定能做到。當(dāng)然課設(shè)也有很多的不足，由于剛學(xué)完數(shù)據(jù)結(jié)構(gòu)沒多久，因此沒有建立一個(gè)系統(tǒng)的知識(shí)框架，在編程時(shí)大體上還是延續(xù)C的思路，并沒有過多的采用數(shù)據(jù)結(jié)構(gòu)在算法和效率上進(jìn)行優(yōu)化，這是此次最大的不足，最大的遺憾，也將會(huì)

37、是今后學(xué)習(xí)的重點(diǎn)，我會(huì)吸取教訓(xùn)，好好地再鞏固自己的理論知識(shí)。</p><p>　　當(dāng)然，我能夠成功編譯出來也不是自己一個(gè)人的功勞，離不開同學(xué)，老師的幫助和點(diǎn)播。在此，我要感謝給于過我?guī)椭闹笇?dǎo)老師和熱心的同學(xué)們，謝謝大家，我會(huì)繼續(xù)努力的。</p><p><b>　　6參考文獻(xiàn)</b></p><p>　　[1]嚴(yán)蔚敏，吳偉民著. 數(shù)據(jù)結(jié)構(gòu)：C