數(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)為鏈?zhǔn)酱鎯Y(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è)計、詳細(xì)設(shè)計、調(diào)試分析、課程總結(jié)、參考文獻(xiàn)等部分。2. 課程設(shè)計論電子文檔及程序源代碼。進(jìn)度安排：本課程設(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 詳細(xì)設(shè)計73.1程序分析73.2程序源代碼74 調(diào)試分析95 課程總結(jié)116參考文獻(xiàn)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 詳細(xì)設(shè)計3.1程序分析建立一個以二叉鏈表方式存儲的二叉樹，建立二叉樹時，按照完全二叉樹的結(jié)點順序輸入，1表示虛結(jié)點，0表示輸入結(jié)束。若不是虛結(jié)點時，則建立一個新結(jié)點，并且將其作為左孩子或右孩子結(jié)點連接到它的父結(jié)點上（第一個結(jié)點無父結(jié)點）；若

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

7、;#define max 10typedef struct nodeint data; /數(shù)據(jù)域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開始編號（按照完全二叉樹的順序標(biāo)記）front=0; /雙親結(jié)點下標(biāo)初值rear=-1; /自身結(jié)點下標(biāo)初值T=NULL; /初始化樹Tprintf("建立

8、二叉樹(1表示虛結(jié)點,0表示輸入結(jié)束):n");scanf("%d",&ch); /按完全二叉樹的順序輸入結(jié)點while(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é)點下標(biāo)加1Brear=S; /將S保存到數(shù)組B中，即從下標(biāo)為0開始存儲if(rear=front) /雙親結(jié)點下標(biāo)與本身下標(biāo)相同時，即無雙親結(jié)點

9、（只有第一個結(jié)點會產(chǎn)生這種情況） T=S;sign+; /結(jié)點的序號加1 else /尋找雙親結(jié)點 if(sign%2=1) Bfront->lchild=S; /S作為左孩子 if(sign%2=0) Bfront->rchild=S;/S作為右孩子front+;/下標(biāo)加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

10、 *T) /中序遍歷二叉樹T，并將每個結(jié)點數(shù)據(jù)存入數(shù)組中 if(T!=NULL) /如果樹不為空 Inorder(T->lchild);printf("%dt",T->data);Btreetemp=T->data;temp+;Inorder(T->rchild);int Judgesort_bitree(int Btree) /判斷中序遍歷后的二叉樹是否是二叉排序樹 int i,sign=1;for(i=0;i<temp-1;i+) /用for循環(huán)語句 看二叉樹是否有序遞增 if(Btreei>Btreei+1) /不是有序遞增的 si

11、gn=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); /中序遍歷二叉樹printf("n");Judgeout(Judgesort_bitree(Btree); /判斷是否為排序二叉樹4 調(diào)試分析實現(xiàn)了設(shè)計的所有要求，選取部分運行示意圖。圖4-1 給定二叉樹是二叉排序樹圖4-2 給定二叉樹不是二叉排序樹結(jié)果分析：成功的編譯了代碼，實驗結(jié)果令人滿意。先說下判斷二叉樹數(shù)否為排序二叉樹的時間復(fù)雜度。二叉樹以二叉鏈表存儲