BST的構(gòu)建與查找討論課報告

BST的構(gòu)建與查找2014.12.72問題描述問題描述利用二叉查找樹（BST）實現(xiàn)一個動態(tài)查找表基本要求使用二叉樹（BST）來實現(xiàn)。二叉樹使用鏈?zhǔn)浇Y(jié)構(gòu)（二叉鏈表）實現(xiàn)。實現(xiàn)BST的構(gòu)建，查找兩個功能。3一、需求分析4

問題分析與任務(wù)定義分析并確定要處理的對象（數(shù)據(jù)）是什么

用戶輸入的節(jié)點個數(shù)和各個節(jié)點數(shù)據(jù)分析并確定要實現(xiàn)的功能是什么

通過用戶輸入的數(shù)據(jù)，構(gòu)建相對應(yīng)的BST，實現(xiàn)節(jié)點的插入和查找功能分析并確定處理后的結(jié)果如何顯示

在DOS界面上輸出查找是否成功以及比較次數(shù)5輸入與輸出合法性合法輸入：節(jié)點個數(shù)：正整數(shù)；節(jié)點數(shù)據(jù)：小數(shù)或整數(shù)合法輸出：查找成功，比較次數(shù)為__；查找失敗，比較次數(shù)為__非法輸入：字母或者中文字符或者～！@#￥%……&這一類的字符，系統(tǒng)應(yīng)提示用戶輸入有誤并重新輸入6輸入輸出形式輸入形式：在該程序中，用戶需要輸入節(jié)點個數(shù)和節(jié)點數(shù)據(jù)以及查找的節(jié)點，節(jié)點數(shù)據(jù)間使用空格隔開，當(dāng)用戶輸入有誤時提示用戶輸入錯誤并重新輸入。具體格式如下：請輸入節(jié)點個數(shù)：請依次節(jié)點數(shù)據(jù)：請輸入需查找的節(jié)點：輸出形式：查找成功，比較次數(shù)為__查找失敗，比較次數(shù)為__測試數(shù)據(jù)（1）請輸入節(jié)點個數(shù)：8

請依次節(jié)點數(shù)據(jù)：12,4,35,78,56,34,89,0

請輸入需查找的節(jié)點：89

查找成功，比較次數(shù)為3請輸入節(jié)點個數(shù)：8

請依次節(jié)點數(shù)據(jù)：12,4,35,78,56,34,89,0

請輸入需查找的節(jié)點：678

查找失敗，比較次數(shù)為37測試數(shù)據(jù)（2）請輸入節(jié)點個數(shù)：c

輸入有誤請重新輸入請輸入節(jié)點個數(shù)：8

請依次節(jié)點數(shù)據(jù)：12,4,35,78,56,&,89.3,A

輸入有誤，請重新輸入請輸入節(jié)點個數(shù)：-1

結(jié)束程序89二、概要設(shè)計抽象數(shù)據(jù)類型

1.在本程序中，需要對插入的節(jié)點進行檢索，而BST的插入和檢索的速率都是很高的，所以我們選用構(gòu)建BST的方法來解決這項問題

2.由用戶輸入的節(jié)點個數(shù)及節(jié)點數(shù)據(jù)均為正整數(shù)，可使用整型數(shù)據(jù)進行存儲，并構(gòu)建一個BST存儲這些節(jié)點數(shù)據(jù)

3.為了節(jié)約空間，使用二叉鏈表實現(xiàn)BST。先定義BST樹節(jié)點ADT，再定義樹的ADT

1011二叉樹節(jié)點的ADTADTNode{數(shù)據(jù)對象：整型數(shù)據(jù)數(shù)據(jù)關(guān)系：沒有前驅(qū)的節(jié)點是根節(jié)點，有前驅(qū)無后繼的節(jié)點是葉節(jié)點基本操作：intval()；//返回結(jié)點的數(shù)值voidsetLeft(Node*);//設(shè)置左子結(jié)點voidsetRight(Node*);//設(shè)置右子節(jié)點Node*Left()const; //返回左子結(jié)點Node*Right()const ;//返回右子結(jié)點}樹的ADT（1）ADTTree{數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R:

若D為空集，則稱為空樹。

否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的

有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

12樹的ADT（2）基本操作：voidclear();//初始化操作boolinsert（constint&）;//插入元素的操作boolfind(constint&)const;//查找元素的操作13算法基本思想（1）

該算法主要包括表的構(gòu)建和查詢兩項：在表的構(gòu)建上，通過用戶輸入的數(shù)據(jù)，將第一個輸入的節(jié)點數(shù)據(jù)存入根節(jié)點中，從第二個節(jié)點元素開始，與根節(jié)點數(shù)據(jù)進行比較，如果該元素大于根節(jié)點的值，則與根節(jié)點的右子節(jié)點相比較，若右子節(jié)點為空，則將該元素存入這個節(jié)點，若不為空，則將該右子節(jié)點視為根節(jié)點，重復(fù)上述步驟。而若該元素小于根節(jié)點的值，則與根節(jié)點左子節(jié)點相比較，若左子節(jié)點為空，則將該元素存入這個節(jié)點，若不為空，則將該左子節(jié)點視為根節(jié)點，重復(fù)上述步驟。直到所有的輸入的元素都存進表中為止；14算法基本思想（2）在表的查詢上，通過用戶輸入的查詢的數(shù)值，將該數(shù)據(jù)與已建好的表的根節(jié)點相比較，比較次數(shù)+1，當(dāng)兩個數(shù)相等時，輸出查找成功，比較次數(shù)為1。當(dāng)該數(shù)小于根節(jié)點的數(shù)時，若左子節(jié)點不為空，則視根節(jié)點的左子節(jié)點為根節(jié)點，將該數(shù)據(jù)與新的根節(jié)點相比較，比較次數(shù)加1，重復(fù)上述步驟，直到左子節(jié)點為空。當(dāng)該數(shù)大于根節(jié)點的數(shù)時，若右子節(jié)點不為空，則視根節(jié)點的右子節(jié)點為根節(jié)點，將該數(shù)據(jù)與新的根節(jié)點相比較，比較次數(shù)加1，重復(fù)上述步驟，直到兩個數(shù)相等或者直到子節(jié)點為空時結(jié)束循環(huán)。若找到相等的元素，則輸出查找成功以及相應(yīng)的比較次數(shù)，若子節(jié)點為空時仍然沒有查找到該元素，則輸出未查找到該元素以及相對應(yīng)的查找次數(shù)；15算法基本流程

本程序主要包括輸入、構(gòu)建BST、查詢和輸出四個模塊，其四個模塊如下：輸入模塊：用戶輸入節(jié)點個數(shù)，各節(jié)點數(shù)據(jù)以及要查找的數(shù)據(jù)：構(gòu)建模塊：根據(jù)用戶輸入的節(jié)點個數(shù)及節(jié)點數(shù)據(jù)構(gòu)造對應(yīng)的BST；查詢模塊：根據(jù)用戶輸入的查詢值，在BST中進行查找；輸出模塊：輸出查找成功還是失敗，并返回比較次數(shù)。1617三、詳細(xì)設(shè)計18TreeNodeClassclassNode{private:intdata;//節(jié)點數(shù)據(jù)Node*p1;//指向左子節(jié)點的指針Node*p2;//指向右子節(jié)點的指針public:Node（intit）{data=it;p=NULL;P2=NULL;}//構(gòu)造函數(shù)~Node（）{delete[]p1;delete[]p2;}//析構(gòu)函數(shù)intval(){returndata;} ;//返回結(jié)點的數(shù)值voidsetLeft(Node*it){p1=it;};//設(shè)置左結(jié)

voidsetRight(Node*it){p2=it}; //設(shè)置右結(jié)點Node*Left()const{returnp1;}; //返回左結(jié)點Node*Right()const{returnp2;} ;//返回右結(jié)點}19TreeClass(1)classBST{private:Node*root;//根節(jié)點public:intcount;//查找次數(shù)BST(){root=NULL;}//構(gòu)造函數(shù)~BST(){deleteroop;}//析構(gòu)函數(shù)voidclear(){root=NULL;}//初始化操作

TreeClass(2)boolinsert(constint&it){//元素的插入操作if(root==NULL)root=newNode(it);//傳給根節(jié)點值Node*subroot1=root;Node*subroot2=root;while(subroot1!=NULL){subroot2=subroot1;if(it<subroot1.val())subroot1=subroot1.Left();elsesubroot1=subroot1.Right();}if(subroot2.val()>it)subroot2.setLeft(newNode(it));//設(shè)置左子節(jié)點elsesubroot2.setRight(newNode(it));//設(shè)置右子節(jié)點returntrue;}2021TreeClass(3)boolfind(int&it){//查找操作Node*subroot=root;count=0;//查找次數(shù)while(subroot!=NULL){if(it==subroot.val()){count++;//查找次數(shù)加1returntrue;}//查找成功elseif(it<subroot.val()){subroot=subroot.Left();count++;}//在左子節(jié)點進行查找elseif(it>subroot.val()){subroot=subroot.Right();count++;}//在右子節(jié)點進行查找}returnfalse;//查找失敗}22算法具體步驟

該算法主要包括輸入構(gòu)建BST查找和輸出四個部分，首先由用戶輸入節(jié)點個數(shù)以及各個節(jié)點數(shù)據(jù)以及需要查找的數(shù)據(jù)。然后通過用戶輸入的節(jié)點數(shù)據(jù)依次插入這些數(shù)據(jù)，構(gòu)建一個相對應(yīng)的BST。接著在BST中查找用戶輸入的查找數(shù)：當(dāng)根節(jié)點為空時，輸出查找失敗并輸出比較次數(shù)為0。當(dāng)根節(jié)點不為空時，計數(shù)器count記為0，先比較查找的數(shù)據(jù)it與根節(jié)點的數(shù)據(jù)大小，若it等于根節(jié)點,計數(shù)器+1，輸出“查找成功“與count；若it小于根節(jié)點，則在該節(jié)點的左子節(jié)點上進行查找；若it大于該節(jié)點，則在右子節(jié)點上進行查找，每查找一次，計數(shù)器+1一次。重復(fù)上述步驟，直到找到與it相等的節(jié)點或者節(jié)點為空為止，最后輸出查找成功或失敗以及count。

23算法偽代碼

input（n）;//節(jié)點個數(shù)for(inti=0;i<n;i++){input（num）;//各個節(jié)點數(shù)據(jù)Tree.insert(num);//依次插入輸入的數(shù)據(jù)}input（FindNum）;//查找的數(shù)據(jù)if(Tree.find(FindNum)==true)output:”查找成功,比較次數(shù)為“<<count<<”次”；if(Tree.find(FindNum)==false)output:”查找失敗,比較次數(shù)為“<<count<<”次”；24主程序輸入與建樹查找與輸出創(chuàng)建結(jié)點插入數(shù)據(jù)True輸出“查找成功”與count的值False輸出“查找失敗”與count的值函數(shù)調(diào)用關(guān)系25算法的時空分析

n個元素的BST高度約為logn,而該算法的插入的最壞情況是在BST最底端進行插入，所以插入的時間復(fù)雜度為

Θ（logn），當(dāng)用戶輸入規(guī)模為n個時，插入的算法時間復(fù)雜度為Θ（nlogn）。查找的時間復(fù)雜度最壞情況也是在最底端找到或者查找失敗，時間復(fù)雜度為Θ（logn），

所以算法總時間復(fù)雜度為Θ（nlogn）。輸入格式26輸入：Input（n）;//節(jié)點個數(shù)for(inti=0;i<n;i++){input（num）;Tree.insert(num);}//各節(jié)點數(shù)據(jù)input（FindNum）;//查找的數(shù)請輸入節(jié)