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

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

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

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

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

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

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

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

9、 if(sign%2=0) bfront-rchild=s;/s作為右孩子front+;/下標加1，即尋找下一個雙親結點 sign+;/結點序號加1 else /輸入結點為虛結點if(sign%2=0) /為右子樹時front+; /雙親結點加1 即下一個雙親結點sign+; /結點序號加1 scanf(%d,&ch);return t;void inorder(bitree *t) /中序遍歷二叉樹t，并將每個結點數據存入數組中 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 調試分析實現了設計的所有要求，選取部分運行示意圖。圖4-1 給定二叉樹是二叉排序樹圖4-2 給定二叉樹不是二叉排序樹結果分析：成功的編譯了代碼，實驗結果令人滿意。先說下判斷二叉樹數否為排序二叉樹的時間復雜度。二叉樹以二叉鏈表存儲，在建立二叉樹，中序遍歷二叉樹和判別時的時間復雜度都為o(n)。再說下編程遇到的問題，編程的關鍵是要建立一棵二叉樹和判別是否為排序二叉樹。其中判斷時，用到了遞歸的思想。調試時也遇到了一些問題，由于對一些頭文件的不熟悉，缺少，導致程序無法運行等小錯

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

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