BST實現(xiàn)動態(tài)查找表

1、HUNANUNIVERSITY課程實習(xí)報告題目：BST實現(xiàn)動態(tài)查找表學(xué)生學(xué)生學(xué)號專業(yè)班級計算機科學(xué)與技術(shù)指導(dǎo)老師曉鴻完成日期、需求分析1、程序任務(wù)：本程序是利用二叉查找樹（BST）來實現(xiàn)；二叉樹使用鏈?zhǔn)浇Y(jié)構(gòu)（二叉鏈表）實現(xiàn);本程序要實現(xiàn)BST的構(gòu)建，查找兩個功能。2、輸入形式：整數(shù)n/BST的節(jié)點個數(shù)n/n個數(shù)據(jù)數(shù)據(jù)x/查找此數(shù)據(jù)3、輸出形式：查找成功整數(shù)m（次數(shù)）返回成功和查找時比較的次數(shù)或：查找不成功整數(shù)m（次數(shù)）返回不成功和查找時比較的次數(shù)4、測試數(shù)據(jù)：輸入：8/BST的節(jié)點個數(shù)34,76,45,18,26,54,92,65/8個數(shù)據(jù)輸入：45/查找45輸出：查找成功3/返回成功和查找時

2、比較的次數(shù)輸入：34/查找34輸出：查找成功1/返回成功和查找時比較的次數(shù)輸入：100/查找100輸出：查找不成功3返回成功和查找時比較的次數(shù)二、概要設(shè)計抽象數(shù)據(jù)類型以正整數(shù)儲存用戶輸入節(jié)點個數(shù)，浮點小數(shù)存儲用戶輸入的數(shù)據(jù)。要實現(xiàn)動態(tài)查找表，二叉查找樹BST的效率很高，因此用BST實現(xiàn)，二叉查找樹定義如下：ADTBST（數(shù)據(jù)對象：D=具有相同特性的一組數(shù)據(jù)元素數(shù)據(jù)關(guān)系：若D為空集，則稱為空樹。否則：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root;（2）當(dāng)n>1時，其余結(jié)點可分為m（m>0）個互不相交的有限集Ti、Tr,其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

3、K,對于任意結(jié)點，設(shè)其值為K,則該結(jié)點左子樹中任意一個結(jié)點的值都小于右子樹中任意一個結(jié)點的值都大于等于K?；静僮鳎篒nitBST(BST&)/初始化二叉樹InitBSTNode(BSTNode*)/初始化結(jié)點clearBST(BSTNode*)/銷毀二叉樹結(jié)構(gòu)insert(BST&,Elem&)/插入結(jié)點find(BST&,Elem&,intcount)/查找結(jié)點，記錄查找次數(shù)ADTBST算法的基本思想根據(jù)題目要求，用二叉查找樹實現(xiàn)動態(tài)查找表。首先將輸入的元素插入BST中。判斷輸入要查找的元素是否在BST中，遞歸比較要查找的元素與當(dāng)前元素的值的大小，若

4、小于當(dāng)前值，則查找其左子樹；若大于，則查找其右子樹。設(shè)置一個計數(shù)器，每查找一次則加一。如果找到，則輸出位置和查找次數(shù)。程序的流程程序由三個模塊組成：(1) 輸入模塊：輸入結(jié)點數(shù)目初始數(shù)據(jù)，構(gòu)建二叉查找樹(2) 查找模塊：判斷需要查找的值是否在該BST中輸出模塊：輸出查找成功與否，并輸出比較的次數(shù)三、詳細(xì)設(shè)計算法的具體步驟插入元素e時，先判斷該二叉樹是否為空，若為空，將e作為該二叉樹的根節(jié)點。否則，從根節(jié)點開始，比較e與節(jié)點n的大小。如果e的值更小，判斷n的左子樹是否為空，若為空，將e作為節(jié)點n的左孩子并返回e,否則比較e與n左孩子的值，依此循環(huán)下去；如果e的值更大，判斷n的右子樹是否為空，若為

5、空，將e作為節(jié)點n的右孩子并返回e,否則比較e與n右孩子的值，依此循環(huán)下去。查找元素時，從根節(jié)點開始，比較e與節(jié)點x的大小，若相等，返回true;如果e比節(jié)點x的值小，判斷x的左子樹是否為空，若為空，返回false,不為空則比較e與x左孩子的值，依次循環(huán)下去；如果e比節(jié)點x的值大，判斷x的右子樹是否為空，若為空，返回false,不為空則比較e與x右孩子的值，依次循環(huán)下去。物理數(shù)據(jù)類型動態(tài)查找表的數(shù)據(jù)為小數(shù)或整數(shù)，用float類型保存。typedeffloatElemType;為了提高空間利用率，用鏈表來實現(xiàn)BST,由于BST是二叉樹，每個節(jié)點有左右兩個節(jié)點，所以用二叉鏈表實現(xiàn)。typedefs

6、tructBSTNode(ElemTypedata;structBSTNode*lchild,*rchild;BSTNode;typedefstructBST(BSTnode*root;BST;基本操作：boolInitBST(BST&b)/初始化二叉樹(b.root=NULL;returnture;boolInitBSTNode(BSTNode*&n)/初始化節(jié)點(n=(BSTNode*)malloc(sizeof(BSTnode);(*n).lchild=NULL;(*n).rchild=NULL;returnture;boolclearBST(BSTNode*&n

7、)/銷毀BST(if(n)returnfalse;if(*n).lchild)clearBST(*n).lchild);if(*N).rchild)clearBST(*n).rchild);free(n);returnture;boolinsert(BST&b,ElemTypee)/把結(jié)點插入BST(BSTNode*n,*m;InitBSTNode(n);(*n).data=e;if(b.root=NULL)(b.root=n;returnture;m=b.root;while(1)/循環(huán)比較(if(e<(*m).data)/小于根節(jié)點則插入左子樹(if(*m).lchild=N

8、ULL)(*m).lchild=m;/給左孩子賦值returnture;elsem=(*m).lchild;continue;/跳出此次循環(huán)，開始下一次else/大于根節(jié)點則插入右子樹(if(*m).rchild=NULL)(*m).rchild=n;/給右孩子賦值returnture;elsem=(*m).rchild;continue;/跳出此次循環(huán)，開始下一次boolfind(BSTb,ElemTypee,int&count)/查詢元素e,記錄比較的次數(shù)，查詢成功返回ture，否則返回false(intcount=0;BSTnode*x=b.root;while(1)/循環(huán)比較(

9、count+;/設(shè)置計數(shù)器if(e<(*x).data)/小于根節(jié)點則在左子樹中查找(if(*x).lchild=NULL)returnfalse;/左子樹為空則查找失敗x=(*x).lchild;/繼續(xù)與左孩子的值比較continue;if(e>(*x).data)/大于根節(jié)點則在右子樹中查找(if(*x).rchild=NULL)returnfalse;/右子樹為空則查找失敗x=(*x).rchild;/繼續(xù)與右孩子的值比較continue;if(e=(*x).data)returnture;算法的時空分析0(log(n),最差情況為查找元素需要的比較次數(shù)由樹的深度決定。因此平

10、均情況為0(n)。輸入和輸出的格式輸入請輸入樹的節(jié)點數(shù)目：/等待輸入請輸入所有節(jié)點數(shù)據(jù)：等待輸入請輸入要查找的數(shù)據(jù)：/等待輸入輸出查找成功，查找次數(shù)：/輸出次數(shù)或查找失敗，查找次數(shù)：輸出次數(shù)四、測試結(jié)果typedeffloatElemType;附錄：源代碼#include<iostream>#include<stdlib.h>usingnamespacestd;typedefstructBSTNode(ElemTypedata;structBSTNode*lchild,*rchild;BSTNode;typedefstructBST(BSTNode*root;BST;b

11、oolInitBST(BST*b)/初始化二叉樹(b->root=NULL;returntrue;boolInitBSTNode(BSTNode*&n)/初始化節(jié)點(n=(BSTNode*)malloc(sizeof(BSTNode);(*n).lchild=NULL;(*n).rchild=NULL;returntrue;boolclearBST(BSTNode*&n)/銷毀BST(if(n)returnfalse;if(*n).lchild)clearBST(*n).lchild);if(*n).rchild)clearBST(*n).rchild);free(n);

12、returntrue;boolinsert(BST*b,ElemTypee)/把結(jié)點插入BST(BSTNode*n,*m;InitBSTNode(n);(*n).data=e;if(b->root=NULL)(b->root=n;returntrue;m=b->root;while(1)/循環(huán)比較(if(e<(*m).data)/小于根節(jié)點則插入左子樹(if(*m).lchild=NULL)(*m).lchild=n;/給左孩子賦值returntrue;elsem=(*m).lchild;continue;else/大于根節(jié)點則插入右子樹(if(*m).rchild=N

13、ULL)(*m).rchild=n;/給右孩子賦值returntrue;elsem=(*m).rchild;continue;boolfind(BST*b,ElemTypee)/查詢元素e,記錄比較的次數(shù)查詢成功返回true,否則返回false(intcount=0;BSTNode*x=b->root;while(1)/循環(huán)比較(count+;/設(shè)置計數(shù)器if(e<(*x).data)/小于根節(jié)點則在左子樹中查找(if(*x).lchild=NULL)(cout<<"查找失敗，查找次數(shù)："<<count<<endl;retur

14、nfalse;/左子樹為空則查找失敗x=(*x).lchild;/繼續(xù)與左孩子的值比較continue;if(e>(*x).data)/大于根節(jié)點則在右子樹中查找if(*x).rchild=NULL)(cout<<"查找失敗，查找次數(shù)："<<count<<endl;returnfalse;/右子樹為空則查找失敗x=(*x).rchild;/繼續(xù)與右孩子的值比較continue;if(e=(*x).data)(cout<<"查找成功，查找次數(shù)："<<count<<endl;cout<<count;returntrue;voidmain()(intn,m=0,count;BSTb;InitBST(&b);cout<<"請輸入樹的節(jié)點數(shù)目："<<endl;cin>>n;ElemType*p=newElemTypen;co