利用二叉排序樹對一組數據排序并查找元素

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

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

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

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

5、inklist p,q;prin tf(請輸入數的個數:)；scanf(%d,&n);prin tf(請輸入待排序的數: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;已排序序列的輸出與查找元素函數:對二叉樹進行中序

6、遍歷，并在訪問節(jié)點的同時 以 m 計數器記下已訪問節(jié)點的個數，同時將該節(jié)點數據與待查找數據比較，如果相等，則用n記下此時的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;主函數模塊，其中a為待排序數的個數，BT為二叉排序樹的根節(jié)點 int main()int a,t,n=0;Linklist BT=NULL;BT=build(BT);prin tf(請輸入待查找元素:)；scanf(%d,&a);prin tf(排序結果為:n); t=visit(BT,a,n);printf(n);if(n!=0)printf(待查找元素存在,且在已排序序列的第%d位!n,n); else prin

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