湖南大學數(shù)據(jù)結構BST的實現(xiàn)和插入

1、課程實習報告目:BST 的實現(xiàn)和插入學生姓名學生學號李曉鴻專業(yè)班級指導老師完成日期問題描述利用二叉查找樹（ BST ）實現(xiàn)一個動態(tài)查找表?；疽?1)(2)(3)使用二叉樹（ BST ）來實現(xiàn)。 二叉樹使用鏈式結構（二叉鏈表）實現(xiàn)。 實現(xiàn) BST 的構建，查找兩個功能。實現(xiàn)提示輸入：8/BST 的節(jié)點個數(shù)34, 76, 45, 18, 26, 54, 92, 65 /8 個數(shù)據(jù)45/ 查找 45 輸出：查找成功 3 / 34/ 查找 34 輸出：查找成功 1 /100/ 查找 100 輸出：查找不成功 3/返回成功和查找時比較的次數(shù)返回成功和查找時比較的次數(shù)返回成功和查找時比較的次數(shù)、需求分

2、析二叉排序樹又稱二叉查找樹 其定義為：二叉排序樹或者是空樹，或者是滿足如下性質的二叉樹： 若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值； 若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值； 左、右子樹本身又各是一棵二叉排序樹。上述性質簡稱二叉排序樹性質 （BST 性質），故二叉排序樹實際上是滿足 BST 性質的二叉樹。1. 輸入的形式和輸入值的范圍： 初始化時需要輸入初始化時輸入的數(shù)據(jù)個數(shù)， 以及這一組需 要輸入的數(shù)據(jù)。由于 BST 的性質，數(shù)據(jù)為關鍵碼（即可以比較大?。?，為簡單起見，均設為 整數(shù)類型，查找時需要輸入被查找的數(shù)據(jù)對象，也為整數(shù)類型2. 輸出的形式： 查找時

3、如果在存儲的數(shù)據(jù)中查找到被查找的數(shù)據(jù)，需要顯示查找成功，并顯 示查找時比較的次數(shù)， 如果查找不成功， 也需要顯示查找不成功， 并輸出查找時比較的次數(shù)。3. 功能 :建立存儲數(shù)據(jù)的結構， 初始化時將輸入的數(shù)據(jù)存儲， 在查找時能夠在存儲的數(shù)據(jù)中進 行搜索以尋找被查找的數(shù)據(jù)， 并進行相關顯示。 并且對于輸入的不符合規(guī)范的數(shù)據(jù)個數(shù)與被 查找數(shù)據(jù)要求能報錯。4. 測試數(shù)據(jù)輸入：8/BST 的節(jié)點個數(shù)34, 76, 45, 18, 26, 54, 92, 65 /8 個數(shù)據(jù)45/查找 45輸出：查找成功，查找了3 次/ 返回成功和查找時比較的次數(shù)34/查找 34 輸出：查找成功，查找了1 次/ 返回成功和

4、查找時比較的次數(shù)100/ 查找 100 輸出：查找不成功查找了3 次/ 返回成功和查找時比較的次數(shù)二、概要設計1.抽象數(shù)據(jù)類型 由于 BST 的特殊性，需要比大小，于是需要關鍵碼，這里選取整數(shù)作為關鍵碼1)ADT BinNode數(shù)據(jù)對象 ： D=ai|ai<R數(shù)據(jù)關系 ：R1=<ai-1,ai>|ai-1,ai<D ,i=2,3,4基本操作 ：int val() /返回結點的數(shù)值Void setValconst Elem&) / 設置節(jié)點的值inline BinNode* left()const /獲取左結點inline BinNode* right()cons

5、t /獲取右結點void setLeft(Node* it) /設置左結點void setRight(Node* it) /設置右結點Bool isLeaf/ 是葉子節(jié)點嗎2)ADT BST數(shù)據(jù)對象BinNode數(shù)據(jù)關系二叉查找樹基本操作searchTree(Node* subroot,int data)/執(zhí)行查找基本操作的函數(shù)需要一個數(shù)據(jù)作為被查找的數(shù)據(jù)，查找成功，或失敗進行相關顯示，輸出比較次數(shù)。creatTree(Node* subroot,int data)/執(zhí)行插入的基本操作的函數(shù)需要一個數(shù) 據(jù)作為輸入的值，一個 數(shù)據(jù)為將要被處理的樹，其將輸入的值放在樹中合 適的位置。2.算法的基本

6、思想(1)建樹<1>建立空樹；<2>取數(shù)值建立新節(jié)點；<3>新節(jié)點內(nèi)的數(shù)值與樹根節(jié)點比值，若根節(jié)點為空，新節(jié)點為根節(jié)點(利用插入操作)。若新節(jié)點內(nèi)數(shù)值比根節(jié)點數(shù)值大，新節(jié)點進去根節(jié)點右子樹，重復<3>，若新節(jié)點內(nèi)數(shù)值比根節(jié)點數(shù)值小，新節(jié)點進去根節(jié)點左子樹，重復 <3>，直到無新節(jié)點建立； 利用遍歷與 BST 特性完成查找：(2)查找<1>要查詢的數(shù)值與根節(jié)點比值，若要查詢的數(shù)值比根節(jié)點數(shù)值大，新節(jié)點進去根節(jié)點右 子樹，重復 <1>，若要查詢的數(shù)值比根節(jié)點數(shù)值小，新節(jié)點進去根節(jié)點左子樹，重復<1>，直

7、到找到這個數(shù)，或者比較到了葉子節(jié)點。(3)主函數(shù)<1>創(chuàng)建一個結點的類<2>提示用戶輸入數(shù)據(jù)的個數(shù) M，此處進行異常處理，若 <3>循環(huán)輸入數(shù)據(jù)， 調用插入函數(shù)創(chuàng)建功的個數(shù)與 M 相等為止。都進行相關的顯示，并輸入查找的次數(shù)<4>輸入查找的數(shù)據(jù)，查找成功或不成功，M 小于 0 ，則報錯。BST，若輸入的不為整數(shù)，則重新輸入，直到輸入成3.程序的流程程序由三個模塊組成：BST 所需的節(jié)點個數(shù)與節(jié)點內(nèi)存儲的值，建立(1) 初始化模塊： 完成輸入初始化 BST。(2) 查找模塊： 實現(xiàn)在 BST 內(nèi)查找元素值的功能。(3) 輸出模塊： 輸出每次查找的結

8、果和比較的次數(shù)。三、詳細設計1.物理數(shù)據(jù)類型(1)葉子節(jié)點的基本操作BST() root = NULL; nodecount = 0; / 建立空樹BST() clearhelp(root); void clear() clearhelp(root); root = NULL;nodecount = 0; bool insert(const Elem& e) /插入root = inserthelp(root, e);/inserthelp 具體實現(xiàn) nodecount+;return true; bool find(const Key& K, Elem& e ， in

9、t& c) const /查找 return findhelp(root, K, e,c); /findhelp 具體實( 2)樹的操作bool searchTree(Node* subroot,int data) / 在結點 subroot 中查找數(shù)據(jù) data ， 二叉查找樹if(subroot!=NULL)/ 如果指針不指向空i+;/ 記住，每次調用函數(shù)時 i 初始為 0 if(data<subroot->data)return searchTree(subroot->pLeftChild,data);/ 值小，訪問結點左子樹else當 data 比結點中的if

10、(data>subroot->data)return searchTree(subroot->pRightChild,data);/ 中的值大，訪問結點右子樹else當 data 比結點/if(data=subroot->data) cout<<" 查找成功 "cout<<" 查找了 "<<i<<" 次 "<<endl; return true;若相等，查找成功，進行相關輸出等 elsecout<<" 查找不成功 " c

11、out<<" 查找了 "<<i<<" 次 "<<endl;return false; / 若指針指向空，知未查找到，進行相關輸出bool creatTree(Node* subroot,int data)if(*subroot!=NULL)/ 指針所指不為空當 data 比結點中的值 if(data<(*subroot)->data) creatTree(&(*subroot)->pLeftChild),data);/ 小，訪問結點左子樹 elseif(data>(*subr

12、oot)->data) creatTree(&(*subroot)->pRightChild),data);/ data 比結點中的值大，訪問結點右子樹else*subroot=new Node;(*subroot)->data=data;/ 若指針指向空，新建結點，將 data 的值放入 return true;2. 算法的時空分析 (1)關于空間開銷，由于我們的二叉查找樹為指針型的，空間開銷正比于結點個數(shù)，即設每個結點中數(shù)據(jù)的空間開銷為a,每個指針的空間開銷為b則樹的空間(M個結點)開銷 0 (M*(a+2*b)( 2)關于時間開銷，新建樹時的時間開銷與插入的數(shù)據(jù)在原有樹的結點的數(shù)據(jù)的值中的大小關系有關，與原有樹的層數(shù)有關，無法精確分析，設某時刻的樹的層數(shù)為n則最小時間開銷為常數(shù)，最大時間開銷為0 n查找時的時間開銷也如此3.函數(shù)的調用關系圖提示用戶輸入節(jié)點的個數(shù)和數(shù)值建立BST查找數(shù)值輸出4.輸入和輸出的格式 輸入1建樹:請輸入請輸入數(shù)據(jù)個數(shù)：提示輸入等待輸入請輸入數(shù)據(jù)：提示輸入2查找:請輸入欲查找的數(shù)：提示輸入 等待輸入輸出1.成功:查找成功，查找了 i次/i為查找的次數(shù)2.失敗:查找不