《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告專(zhuān)業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)： 081 計(jì)算機(jī)學(xué)號(hào)： 08136101姓名：學(xué)期： 20XX-20XX 學(xué)年第 2 學(xué)期設(shè)計(jì)題目： _判別否為二叉排序樹(shù) 設(shè)計(jì)地點(diǎn)： _西區(qū)理工樓 303指導(dǎo)教師： _唐開(kāi)山 完成日期： _20XX-6-6_ 成績(jī)： 一、需求分析及規(guī)格說(shuō)明 要求：建立一棵二叉樹(shù)，然后判別該二叉樹(shù)是否為二叉排序樹(shù)。規(guī)格說(shuō)明： 空樹(shù)默認(rèn)為二叉排序樹(shù)，沒(méi)有作為輸入考慮對(duì)象。二、概要設(shè)計(jì)程序設(shè)計(jì)比較簡(jiǎn)單，定義樹(shù)的結(jié)構(gòu)，創(chuàng)建樹(shù) CreateBitTree(), InitTree()為空樹(shù)，用遞歸方法先序遍歷二叉樹(shù) DLR() 來(lái)幫助顯示輸入的樹(shù) .根據(jù)二叉排序樹(shù)的定義

2、 :矚慫潤(rùn)厲釤瘞睞櫪廡賴(lài)賃軔朧。二叉排序樹(shù)( Binary Sort Tree )又稱(chēng)二叉查找樹(shù)。 它或者是一棵空樹(shù)；或者是具有下列性質(zhì)的二叉樹(shù)：(1) 若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；(2) 若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；(3) 左、右子樹(shù)也分別為二叉排序樹(shù)；使用了輔助函數(shù) SortTree()在main函數(shù)中調(diào)用幫助判斷所建二叉樹(shù)是否為二叉排序樹(shù)三、詳細(xì)設(shè)計(jì)#include<stdio.h> #include<stdlib.h>#include<iostream.h>typedef char Elem

3、type;typedef struct BitNodeElemtype data;BitNode *Lchild，*Rchild;/ 左，右孩子指針BitNode， *BitTree;void InitTree(BitTree *BT) / 構(gòu)造一個(gè)空二叉樹(shù)BT=NULL;int CreateBitTree(BitTree &BT)/ 構(gòu)造一個(gè)二叉樹(shù)Elemtype ch;cin>>ch;if(ch='#') BT=NULL;/ 建空樹(shù)elseif(!(BT=(BitNode*)malloc(sizeof(BitNode)exit(1);BT->dat

4、a=ch;CreateBitTree(BT->Lchild);CreateBitTree(BT->Rchild);return 1;void DLR(BitTree root)/ 遞歸方法先序遍歷二叉樹(shù)if(root!=NULL)printf("%c ",root->data);DLR(root->Lchild);DLR(root->Rchild);void SortTree(BitTree &T)/ 判斷是否是二叉排序樹(shù)BitTree s100;BitTree t100;int top=0;int k=0;while(T!=NULL|

5、top!=0)while(T)s+top=T;T=T->Lchild;if(top!=0)tk+=stop;T=stop->Rchild;for(int i=0;i<k-1;i+)if(ti->data>=ti+1->data)printf(" 不是二叉排序樹(shù) n");return; 聞創(chuàng)溝燴鐺險(xiǎn)愛(ài)氌譴凈禍測(cè)樅。 printf(" 是二叉排序樹(shù) n");void main()int flag=0;int t ;BitTree T;while(1)printf("*二叉排序樹(shù) *n");殘騖樓諍錈瀨濟(jì)

6、溆塹籟婭騍東。printf("1、建立二叉鏈表 n");printf("2、遍歷二叉樹(shù)輸出 n");printf("3、判斷二叉樹(shù)是否是二叉排序樹(shù) n");printf("0、退出操作 n" );printf("*n");釅錒極額閉鎮(zhèn)檜豬訣錐顧葒鈀。scanf("%d",&t);switch(t)case 1:printf("請(qǐng)輸入字符串構(gòu)造二叉樹(shù)(#代表空樹(shù)):n");flag=CreateBitTree(T);getchar();break;c

7、ase 2:if(flag=1) if(T!=NULL)printf(”用遞歸算法先序遍歷二叉樹(shù)：n");DLR(T);pri ntf("n");elseprintf("二叉樹(shù)為空!n");elseprintf("請(qǐng)先建立二叉樹(shù)!n");break;case 3:if(flag=1)if(T!=NULL)SortTree(T);pri ntf("n"); elseprintf("二叉樹(shù)為空!n");elseprintf("請(qǐng)先建立二叉樹(shù)!n"); break;case 0:exit(0);break;default:printf("輸入錯(cuò)誤!n");四、調(diào)試分析調(diào)試通過(guò)，輸入時(shí)要注意，輸入的方式不同可能得到的結(jié)果不一樣，雖然遍歷輸出的結(jié)果看來(lái)一樣，但判 斷是否為二叉排序樹(shù)時(shí)就不相同了。由于構(gòu)造時(shí)，輸入方式不同，導(dǎo)致構(gòu)造的樹(shù)結(jié)構(gòu)不一樣，雖然數(shù)據(jù)一 樣，但樹(shù)的結(jié)構(gòu)有差異，判斷就不相同了。彈貿(mào)攝爾霽斃攬磚鹵廡詒爾膚。五、測(cè)試結(jié)果鵜三麴鮭是二叉排序樹(shù)0.退岀操作2用遞歸算法先序遍歷二叉樹(shù): 虹bItEiMKJtiMKMiilOtMjiMJtItaOtMjIOtJtICX