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

1、課程設(shè)計任務(wù)書學(xué) 院專 業(yè)學(xué) 生 姓 名學(xué) 號題 目判別給定的二叉樹是否為二叉排序樹內(nèi)容及要求：設(shè)計內(nèi)容：判別給定的二叉樹是否為二叉排序樹，設(shè)此二叉樹以二叉鏈表存儲，且樹中結(jié)點的關(guān)鍵字均不相同。為實現(xiàn)上述功能，需要解決的關(guān)鍵問題是：建立一棵二叉樹及判定二叉樹過程。要求：1.設(shè)計數(shù)據(jù)結(jié)構(gòu)：建立的是二叉樹，所以邏輯結(jié)構(gòu)為樹形結(jié)構(gòu)。定義存儲結(jié)構(gòu)為鏈式存儲結(jié)構(gòu)，用typedef定義結(jié)點的結(jié)構(gòu)體。2.在turboc或兼容環(huán)境完成上述題目的代碼編寫與調(diào)試；3.程序運行界面交互性好；輸入輸出數(shù)據(jù)時，應(yīng)該有相應(yīng)的提示。4.給出兩組測試數(shù)據(jù)，可以按路徑覆蓋的方法給出兩組主要的測試數(shù)據(jù)。任務(wù)交付：1. 課程設(shè)計論

2、文，包括需求分析、概要設(shè)計、詳細設(shè)計、調(diào)試分析、課程總結(jié)、參考文獻等部分。2. 課程設(shè)計論電子文檔及程序源代碼。進度安排：本課程設(shè)計時間為17、18教學(xué)周。其中包含設(shè)計、代碼調(diào)試、課程設(shè)計論文撰寫、驗收與答辯幾個階段。第1周 查找資料、完成初步設(shè)計、代碼設(shè)計與初步調(diào)試；第2周 調(diào)試、測試、驗收、課程設(shè)計論文撰寫、答辯。指導(dǎo)教師（簽字）：2011年 12月16日學(xué)院院長（簽字）： 2011年12月16日目錄1 需求分析32 概要設(shè)計42.1存儲結(jié)構(gòu)設(shè)計說明42.2程序功能圖42.3算法流程圖53 詳細設(shè)計73.1程序分析73.2程序源代碼74 調(diào)試分析95 課程總結(jié)116參考文獻121 需求分析

3、7780905068883456 圖1-1 二叉樹以圖1-1所示的二叉樹為例設(shè)計，建立一個以二叉鏈表方式存儲的二叉樹，輸入結(jié)點信息時按照完全二叉樹的結(jié)點順序輸入（1為虛結(jié)點，0為輸入結(jié)束）。由于一棵二叉排序樹中序遍歷后的序列是遞增有序的，因此可利用中序遍歷一棵二叉樹后的序列是否遞增有序來判斷是否為二叉排序樹。 如圖，二叉樹的結(jié)點輸入順序為77 80 90 50 1 68 88 1 1 34 56 0 （1為虛結(jié)點，0為輸入結(jié)束），中序遍歷之后的順序為50 80 77 34 68 56 90 88 ，由于中序遍歷之后的序列不是遞增有序的，因此可判斷出此二叉樹不是二叉排序樹。2 概要設(shè)計2.1 存

4、儲結(jié)構(gòu)設(shè)計說明 typedef struct nodeint data; /數(shù)據(jù)域node *lchild,*rchild; /左孩子指針，右孩子指針bitree; /結(jié)點的結(jié)構(gòu)體定義 2.2程序功能圖建立二叉樹（按照完全二叉樹的結(jié)點順序輸入）中序遍歷二叉樹，并將結(jié)點保存在數(shù)組中比較數(shù)組元素，看是否有序遞增判斷是否為二叉排序樹 圖2-1 程序功能圖2.3算法流程圖選取部分核心流程圖如下：開始初始化二叉樹bitree *creatree()inorder(bitree *t)judgeout(judgesort_bitree(btree)判斷是否為二叉樹是二叉排序樹不是二叉排序樹序樹結(jié)束yn結(jié)束

5、圖2-2 主要流程圖開始sign=0,front=0,rear=-1,t=nullch!=0?ch!=1?rear+sign%2=0?front+sign+yynynbrear=srear=front創(chuàng)建結(jié)點synsign%2=1?t=ssign+nybfrontlchild=sbfrontrchild=sfront+sign+n結(jié)束圖2-3 建立二叉樹3 詳細設(shè)計3.1程序分析建立一個以二叉鏈表方式存儲的二叉樹，建立二叉樹時，按照完全二叉樹的結(jié)點順序輸入，1表示虛結(jié)點，0表示輸入結(jié)束。若不是虛結(jié)點時，則建立一個新結(jié)點，并且將其作為左孩子或右孩子結(jié)點連接到它的父結(jié)點上（第一個結(jié)點無父結(jié)點）；若

6、是虛結(jié)點，則將空結(jié)點（null）作為左孩子或右孩子結(jié)點連接到它的父節(jié)點上。判定二叉樹時，中序遍歷整棵二叉樹，訪問根結(jié)點時將根結(jié)點信息存入一個數(shù)組中，以用來比較中序遍歷后序列是否為空。比較數(shù)組元素時，從下標為0的數(shù)組元素開始比較，先將下標為i=0的ai與下標為1的ai+1比較，如果aiai+1，則結(jié)束比較，即該二叉樹不是二叉排序樹，否則繼續(xù)比較，直至比較完整個數(shù)組元素。3.2程序源代碼#include stdafx.h /編寫的任何.cpp文件都必須首先包含stdafx.h#include#include#define max 10typedef struct nodeint data; /數(shù)據(jù)

7、域node *lchild,*rchild; /左孩子指針，右孩子指針bitree; /結(jié)點的結(jié)構(gòu)體定義bitree *bmax;int temp=0;int btreemax;bitree *creatree() /建立二叉樹bitree *t,*s;int ch;int front,rear,sign;sign=0; /結(jié)點的序號從0開始編號（按照完全二叉樹的順序標記）front=0; /雙親結(jié)點下標初值rear=-1; /自身結(jié)點下標初值t=null; /初始化樹tprintf(建立二叉樹(1表示虛結(jié)點,0表示輸入結(jié)束):n);scanf(%d,&ch); /按完全二叉樹的順序輸入結(jié)點w

8、hile(ch!=0) if(ch!=1) /輸入結(jié)點不是虛結(jié)點 s=(bitree *)malloc(sizeof(bitree); /創(chuàng)建新結(jié)點ss-data=ch; /將輸入的數(shù)據(jù)保存到s中s-lchild=s-rchild=null; /將s的左右子樹為空rear+; /結(jié)點下標加1brear=s; /將s保存到數(shù)組b中，即從下標為0開始存儲if(rear=front) /雙親結(jié)點下標與本身下標相同時，即無雙親結(jié)點（只有第一個結(jié)點會產(chǎn)生這種情況） t=s;sign+; /結(jié)點的序號加1 else /尋找雙親結(jié)點 if(sign%2=1) bfront-lchild=s; /s作為左孩子

9、 if(sign%2=0) bfront-rchild=s;/s作為右孩子front+;/下標加1，即尋找下一個雙親結(jié)點 sign+;/結(jié)點序號加1 else /輸入結(jié)點為虛結(jié)點if(sign%2=0) /為右子樹時front+; /雙親結(jié)點加1 即下一個雙親結(jié)點sign+; /結(jié)點序號加1 scanf(%d,&ch);return t;void inorder(bitree *t) /中序遍歷二叉樹t，并將每個結(jié)點數(shù)據(jù)存入數(shù)組中 if(t!=null) /如果樹不為空 inorder(t-lchild);printf(%dt,t-data);btreetemp=t-data;temp+;in

10、order(t-rchild);int judgesort_bitree(int btree) /判斷中序遍歷后的二叉樹是否是二叉排序樹 int i,sign=1;for(i=0;ibtreei+1) /不是有序遞增的 sign=0;break;return sign; void judgeout(int a)/判斷輸出 將sign賦給a if(a=1)printf(給定二叉樹是二叉排序樹!n);if(a=0)printf(給定二叉樹不是二叉排序樹!n);void main()bitree *t;t=creatree(); /建立二叉樹printf(中序遍歷:n);inorder(t); /中

11、序遍歷二叉樹printf(n);judgeout(judgesort_bitree(btree); /判斷是否為排序二叉樹4 調(diào)試分析實現(xiàn)了設(shè)計的所有要求，選取部分運行示意圖。圖4-1 給定二叉樹是二叉排序樹圖4-2 給定二叉樹不是二叉排序樹結(jié)果分析：成功的編譯了代碼，實驗結(jié)果令人滿意。先說下判斷二叉樹數(shù)否為排序二叉樹的時間復(fù)雜度。二叉樹以二叉鏈表存儲，在建立二叉樹，中序遍歷二叉樹和判別時的時間復(fù)雜度都為o(n)。再說下編程遇到的問題，編程的關(guān)鍵是要建立一棵二叉樹和判別是否為排序二叉樹。其中判斷時，用到了遞歸的思想。調(diào)試時也遇到了一些問題，由于對一些頭文件的不熟悉，缺少，導(dǎo)致程序無法運行等小錯

12、誤通過查閱一些資料得到了解決。再有就是由于程序涉及到指針，因此有時指針隨機訪問到系統(tǒng)隱藏空間時會出現(xiàn)異常終端，通過改進，異常出現(xiàn)的幾率大大降低，可認為程序能近似完美運行。最后說下算法的優(yōu)缺點，優(yōu)點是：由于使用二叉鏈表存儲，結(jié)構(gòu)簡單，可以方便的構(gòu)造任何形狀的二叉樹，并可以方便的實現(xiàn)二叉樹的大多數(shù)操作。缺點是：查找當前結(jié)點的雙親結(jié)點操作實現(xiàn)起來比較麻煩。而且存儲效率不高，進一步優(yōu)化的話，可以逐條歸類存儲。算法改進的話，可以調(diào)整下操作界面，使人機交流更簡單，方便用戶操作。5 課程總結(jié) 數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計終于結(jié)束，真的很開心。經(jīng)過一個學(xué)期的學(xué)習(xí)，我覺得課設(shè)是對于我們數(shù)據(jù)結(jié)構(gòu)掌握程度的測驗與評估。這兩周

13、的課設(shè)，從開始的確定命題，到搜集資料，到初步編程，到修改代碼，到最終完成代碼，這是一個學(xué)習(xí)的過程，一個升華的過程。我想課設(shè)的意義也是在于此吧。這個程序由于使用二叉鏈表存儲，結(jié)構(gòu)簡單，可以方便的構(gòu)造任何形狀的二叉樹，并可以方便的實現(xiàn)二叉樹的大多數(shù)操作。但是他也存在不足，查找當前結(jié)點的雙親結(jié)點操作實現(xiàn)起來比較麻煩。而且存儲效率不高，進一步優(yōu)化的話，可以逐條歸類存儲。調(diào)試時也遇到了一些問題，由于對一些頭文件的不熟悉，缺少，導(dǎo)致程序無法運行等小錯誤通過查閱一些資料得到了解決。再有就是由于程序涉及到指針，因此有時指針隨機訪問到系統(tǒng)隱藏空間時會出現(xiàn)異常終端，通過改進，異常出現(xiàn)的幾率大大降低，可認為程序能近似完美運行。雖然剛開始很困難，但是只要你愿意做，就一定能做到。當然課設(shè)也有很多的不足，由于剛學(xué)完數(shù)據(jù)結(jié)構(gòu)沒多久，因此沒有建立一個系統(tǒng)的知識框架，在編程時大體上還是延續(xù)c的思路，并沒有過多的采用數(shù)據(jù)結(jié)構(gòu)在算