利用二叉排序樹對(duì)一組數(shù)據(jù)排序并查找元素

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目: 利用二叉排序樹對(duì)一組數(shù)據(jù)排序并查找元素實(shí)驗(yàn)?zāi)康模?1)熟悉二叉排序樹的生成算法；了解將排序二叉樹轉(zhuǎn)化為有序排列的方法；學(xué)會(huì)在一組數(shù)據(jù)中查找元素。實(shí)驗(yàn)內(nèi)容：建立一組數(shù)據(jù)的二叉排序樹，然后中序遍歷，并查找待查找元素。 一、需求分析1輸入的形式和輸入值的范圍:本程序要求輸入待排序數(shù)的個(gè)數(shù)，并逐個(gè)輸入待排序數(shù)，最 后輸入待查找元素的值。2輸出的形式:按從小到大的順序輸出排過序的數(shù)，并輸出查找結(jié)果，如果存在，還需輸出 待查找數(shù)在已排序序列中的位置。3程序所能達(dá)到的功能:對(duì)確定個(gè)數(shù)的一組數(shù)實(shí)現(xiàn)遞增排序，并查找待查找元素。 4測(cè)試數(shù)據(jù)：待排序數(shù)個(gè)數(shù):5;待排序數(shù):12 43 23

2、 54 8;已存在元素查找:23;不存在的元素查找:10概要設(shè)計(jì)二叉排序樹的生成模塊:根據(jù)二叉排序樹的定義，任一節(jié)點(diǎn)如果有左子樹，其左子 樹各節(jié)點(diǎn)的數(shù)據(jù)必須小于該節(jié)點(diǎn)的數(shù)據(jù)；任一節(jié)點(diǎn)如果有右子樹，其右子樹各節(jié)點(diǎn) 的數(shù)據(jù)必須等于或大于該節(jié)點(diǎn)的數(shù)據(jù)。則可將第一個(gè)數(shù)據(jù)作為整個(gè)二叉排序樹的根 節(jié)點(diǎn)，以后的數(shù)據(jù)都從根節(jié)點(diǎn)起，由上而下逐層與原有節(jié)點(diǎn)的數(shù)據(jù)相比較，若較原 節(jié)點(diǎn)數(shù)值小，則進(jìn)而與其左孩子節(jié)點(diǎn)的數(shù)值比，否則與其右孩子節(jié)點(diǎn)數(shù)據(jù)比，直至 找到一個(gè)節(jié)點(diǎn)相應(yīng)的指針是空指針了，即將新結(jié)點(diǎn)插入此處作為終端節(jié)點(diǎn)。已排序序列的輸出與查找元素模塊:根據(jù)排序二叉樹的結(jié)構(gòu)特點(diǎn)，只要對(duì)該二叉樹 進(jìn)行中序遍歷，即可按從小到

3、大的順序訪問這些數(shù)據(jù)節(jié)點(diǎn)，再在訪問這些節(jié)點(diǎn)的時(shí) 候與待查找元素比較，如果找到，記下該數(shù)據(jù)位置，如果訪問完了還沒找到，則待 查找元素不存在。詳細(xì)設(shè)計(jì)定義結(jié)構(gòu)體變量typedef struct nodeint data;struct node *lchild;struct node *rchild;Lnode,*Linklist;定義指針棧typedef structLinklist dataMAXSIZE;int top;Seqstack;初始化棧函數(shù)void Initstack(Seqstack &s)s.top=-1;判斷?？蘸瘮?shù)，如果棧空返回1，否則返回 0 int StackEmpty(

4、Seqstack &s)if(s.top=-1)return 1;elsereturn 0;入棧函數(shù)void push(Seqstack &s,Linklist x)s.top+;s.datas.top=x;出棧函數(shù)Linklist pop(Seqstack &s)return s.datas.top-;二叉排序樹的生成函數(shù)，具體算法為:讀取一個(gè)待排序數(shù)；生成一個(gè)新節(jié)點(diǎn)，將讀入數(shù)據(jù)賦給新節(jié)點(diǎn)；若根節(jié)點(diǎn)為空，則另根節(jié)點(diǎn)等于該新節(jié)點(diǎn)，否則Q如果小于根節(jié)點(diǎn)，沿左鏈域比較；Q否則沿右鏈域比較；直至到終端，插入該結(jié)點(diǎn)。Linklist build(Linklist BT)int n,i,a100=0;L

5、inklist p,q;prin tf(請(qǐng)輸入數(shù)的個(gè)數(shù):)；scanf(%d,&n);prin tf(請(qǐng)輸入待排序的數(shù):n); for(i=0;idata=ai;p-lchild=NULL;p-rchild=NULL;if(BT=NULL)BT=p; q=p;elseq=BT;while(p-data!=q-data)if(p-datadata)if(q-lchild=NULL)q-lchild=p;else q=q-lchild;elseif(q-rchild=NULL)q-rchild=p;else q=q-rchild;return BT;已排序序列的輸出與查找元素函數(shù):對(duì)二叉樹進(jìn)行中序

6、遍歷，并在訪問節(jié)點(diǎn)的同時(shí) 以 m 計(jì)數(shù)器記下已訪問節(jié)點(diǎn)的個(gè)數(shù)，同時(shí)將該節(jié)點(diǎn)數(shù)據(jù)與待查找數(shù)據(jù)比較，如果相等，則用n記下此時(shí)的m值，如果二叉樹遍歷完了n仍然為0則代表沒找到，最 后返回 n 的值。int visit(Linklist BT,int &a,int &n)int m=0;Linklist p;Seqstack s;Initstack(s);p=BT;push(s,p);while(!StackEmpty(s)while(p-lchild!=NULL) p=p-lchild; push(s,p);dop=pop(s);m+;if(p-data=a)n=m;printf(%d ,p-dat

7、a);while(p-rchild=NULL&!StackEmpty(s); if(p-rchild!=NULL) p=p-rchild; push(s,p);return n;主函數(shù)模塊，其中a為待排序數(shù)的個(gè)數(shù)，BT為二叉排序樹的根節(jié)點(diǎn) int main()int a,t,n=0;Linklist BT=NULL;BT=build(BT);prin tf(請(qǐng)輸入待查找元素:)；scanf(%d,&a);prin tf(排序結(jié)果為:n); t=visit(BT,a,n);printf(n);if(n!=0)printf(待查找元素存在,且在已排序序列的第%d位!n,n); else prin

8、tf(待查找元素不存在!n);return 0;使用說明、測(cè)試分析及結(jié)果程序使用說明：(1)該程序在VC環(huán)境下運(yùn)行；(2) 其余操作按提示進(jìn)行即可。測(cè)試結(jié)果與分析:(1) 已存在數(shù)據(jù)查找測(cè)試G:E 學(xué)習(xí) DS07Deb ugDS07.exe(2)不存在數(shù)據(jù)查找汚數(shù)素 在to 8兀 4w y 需4找G:E 學(xué)習(xí) DS07Deb ugDS07.exe(2)不存在數(shù)據(jù)查找汚數(shù)素 在to 8兀 4w y 需4找：5不he 舉5查為43素y 馨23待果3兀an 天入3人結(jié)2找S 務(wù) 4 幫12杳一es 當(dāng)12羸8待pr：10cont inue回顧與分析:在二叉排序樹中，其節(jié)點(diǎn)是按照左子樹、根、右子樹的次序由小到大排序的 因此在生成模塊中對(duì)每一個(gè)數(shù)據(jù)都需從根節(jié)點(diǎn)開始比較來確定其屬于哪個(gè)節(jié)點(diǎn)的哪個(gè)孩子 而且在序列輸出模塊中采用了二叉樹的中序遍歷以讓所得節(jié)點(diǎn)序列為一個(gè)有序序列。運(yùn)行界面。五、實(shí)驗(yàn)總結(jié)本次程序在排序樹生成模塊中關(guān)于判斷新結(jié)點(diǎn)是否已鏈到排序樹終端的條件