對于二叉排序樹的實現(xiàn)的實踐成果報告

1、對于二叉排序樹的實現(xiàn)的實踐成果報告一、 二叉樹序數(shù)算法的內(nèi)容二叉排序樹的實現(xiàn)，用順序和二叉鏈表作存儲結(jié)構(gòu)。首先，以回車（n）為輸入結(jié)束標志，輸入數(shù)列L，生成一棵二叉排序樹T；然后，對二叉排序樹T作中序遍歷，輸出結(jié)果；最后，輸入元素x，查找二叉排序樹T，若存在含x的結(jié)點，則刪除該結(jié)點，并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；二、 算法流程1. 用C+實現(xiàn)二叉排序樹的源代碼2. 建立一個二叉樹3. 在一棵二叉排序樹中插入一個數(shù)4. 在一個二叉排序樹查找一個數(shù)是否存在5. 在一個二叉排序樹刪除一個給定的值6. 顯示一個二叉排序樹7. 刪除一棵整二叉排序樹8. 進行對二叉樹的基本操作三、 算

2、法的應(yīng)用領(lǐng)域和作用1. 基于二叉排序樹的緩沖機制在污染源監(jiān)控系統(tǒng)中的研究傳統(tǒng)意義上的污染源在線自動監(jiān)控系統(tǒng)的數(shù)據(jù)查詢采用順序查找法，由于其時間復(fù)雜度高，導(dǎo)致在數(shù)據(jù)量巨大的場合下效率低下。 本文研究與實現(xiàn)基于二叉排序樹的數(shù)據(jù)緩沖機制的污染源在線自動監(jiān)控系統(tǒng)，提高監(jiān)測污染物的效率，降低查詢時間復(fù)雜度。 樹形目錄的存儲結(jié)構(gòu)比線性表結(jié)構(gòu)的組織形式更靈活，所以對于數(shù)據(jù)量大的信息通常采用樹形結(jié)構(gòu)存儲。污染物數(shù)據(jù)存儲于關(guān)系數(shù)據(jù)庫中，查詢時需要頻繁地訪問數(shù)據(jù)庫。 從數(shù)據(jù)庫中獲得一個數(shù)據(jù)項所需要的計算機指令數(shù)往往比從服務(wù)器中獲得一個文件要大一到兩個數(shù)量級，影響系統(tǒng)運行的整體性能。在多數(shù)系統(tǒng)中對某一對象重復(fù)訪問，

3、 通常將生成數(shù)據(jù)進行緩沖處理，有利于系統(tǒng)性能的提高。2. 緩沖實例的產(chǎn)生2.1系統(tǒng)緩沖機制緩沖機制主要是基于被訪問數(shù)據(jù)以減少網(wǎng)絡(luò)傳輸、提高檢索效率為目的。 動態(tài)的緩沖是客戶端通過網(wǎng)絡(luò)訪問服務(wù)器動態(tài)生成的，廣域網(wǎng)環(huán)境中客戶端請求的響應(yīng)時間與請求傳輸時間、協(xié)議處理時間、數(shù)據(jù)裝載時間、數(shù)據(jù)傳輸時間、數(shù)據(jù)表示時間有關(guān)。在這種環(huán)境中，緩沖主要是為了減少請求時間和數(shù)據(jù)的傳輸時間。緩沖數(shù)據(jù)主要分為兩部分，主要存儲在服務(wù)器端。數(shù)據(jù)對象的集合較為巨大，僅僅存放于硬盤上會直接影響訪問速度。緩沖區(qū)位于服務(wù)器的內(nèi)存中，順序存儲臨時存放生成的數(shù)據(jù)，通常使用簡單的有限空間管理機制來限制緩沖數(shù)據(jù)所占用的空間，采用二叉排序樹

4、手段存放數(shù)據(jù)，可以提高檢索速率，縮短查詢時間。2.2系統(tǒng)緩沖實例污染源附近現(xiàn)場機負責采集污染物數(shù)據(jù)， 通過傳輸網(wǎng)絡(luò)傳送到上位機（即服務(wù)器），服務(wù)器接受數(shù)據(jù)并進行分析入庫，在其他客戶端上可以隨時查詢這些已入庫的數(shù)據(jù)。 多臺監(jiān)控設(shè)備定時將數(shù)據(jù)傳輸給數(shù)據(jù)采集器，再由數(shù)據(jù)采集器發(fā)送給服務(wù)器，將數(shù)據(jù)包從數(shù)據(jù)采集器到上位機的傳輸采用 GPRS 無線網(wǎng)絡(luò)，使用 TCPIP 協(xié)議。 服務(wù)器端將數(shù)據(jù)包進行解包分析，解析出各個監(jiān)控設(shè)備的參數(shù)值，并將其存入動態(tài)緩沖區(qū)，然后將它們對應(yīng)入庫。 客戶端通過 BS 系統(tǒng)對數(shù)據(jù)庫中的信息進行查詢，根據(jù)不同的設(shè)置條件相應(yīng)生成表格形式和曲線圖形式的圖像， 查詢條件的設(shè)置包括時間、

5、名稱、參數(shù)等。 服務(wù)器根據(jù)訪問對象的查找，被訪問對象根據(jù)各種因素生成預(yù)期的數(shù)據(jù)集合，若符合要求，結(jié)束查詢并反饋給客戶，不符合要求則繼續(xù)添加查詢，直至符合客戶端要求。3. 二叉排序樹應(yīng)用于緩沖實例3.1 建立二叉排序樹二叉排序樹的構(gòu)造方法是根據(jù)客戶端提交的查詢條件建立包含子樹的數(shù)據(jù)結(jié)構(gòu)， 以水污染物濃度為關(guān)鍵字建立二叉排序樹。在污水中主要有八種污染物：鉛、錳、銅、鋅、鐵、汞、銀、鈹，構(gòu)造一個線性表（ Pb 、 Mn 、 Cu 、 Zn 、 Fe 、 Hg 、 Ag 、 Be ），以鉛為根結(jié)點構(gòu)造二叉排序樹， 其他的結(jié)點參照各種污染物的污染濃度的大小，若小于父結(jié)點的 value 值則將其作為左子樹

6、，反之將其作為右子樹，使新的葉子結(jié)點找到合適的位置插入，這樣生成的二叉排序樹左右子樹仍然滿足二叉排序樹的要求。PId 污染物編號是 int 型數(shù)據(jù)作為結(jié)點的唯一標識， PNa 污染物名稱是 text 型數(shù)據(jù)， Cm 化學符號是 char 型數(shù)據(jù)， Con 污染物濃度是 float 數(shù)據(jù)類型， Fi 記錄父結(jié)點信息， Chi 記錄子節(jié)點信息。四、 算法應(yīng)用的結(jié)果、時間分析和空間分析完成的二叉樹很可能存在某個結(jié)點左、 右子樹的高度之差的絕對值大于 1 ，某結(jié)點左、右子樹的深度之差叫平衡因子，即平衡因子大于 1 ，這樣的二叉樹就不是平衡二叉樹，時間復(fù)雜度就不是最低的，效率也不是最高的。 將構(gòu)造好的二

7、叉樹進行旋轉(zhuǎn)調(diào)整，使其平衡因子不大于 1 。 傳統(tǒng)的旋轉(zhuǎn)算法包括順時針旋轉(zhuǎn)、逆時針旋轉(zhuǎn)、先順時針后逆時針旋轉(zhuǎn)、先逆時針后順時針旋轉(zhuǎn)四種方法。 若有結(jié)點進行插入或刪除，二叉樹就會變得不平衡，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點左、右子樹的高度差。 如果在某一結(jié)點發(fā)現(xiàn)高度不平衡，停止回溯。 從發(fā)生不平衡的結(jié)點起，沿剛才回溯的路徑取直接下兩層的結(jié)點。如果這三個結(jié)點處于一條直線上，則采用單旋轉(zhuǎn)進行平衡化；如果這三個結(jié)點處于一條折線上，則采用雙旋轉(zhuǎn)進行平衡化。 通過對其進行旋轉(zhuǎn)調(diào)整，使其再次成為平衡二叉樹。當插入新的結(jié)點時，先從根結(jié)點進行比較，找到插入位置，并記錄訪問路徑。 從訪問路徑倒數(shù)第二個

8、結(jié)點開始遍歷該子樹，并計算每個結(jié)點的平衡因子，選擇相應(yīng)的調(diào)整函數(shù)。 當刪除某個結(jié)點的時候，需要對刪除結(jié)點位置進行處理，如果該結(jié)點是葉子結(jié)點，可以直接刪除，如果是單枝結(jié)點，葉子結(jié)點取代該結(jié)點后刪除， 若是雙枝結(jié)點則需進一步判斷其平衡因子。 Mn 結(jié)點平衡因子的絕對值大于1 ，對該結(jié)點進行旋轉(zhuǎn)，使其成為平衡二叉樹。用戶對污染物信息查詢時， 輸入污染物的名字轉(zhuǎn)換為對應(yīng)的化學符號，快速與數(shù)據(jù)庫信息比對后，若不存在該污染物，將查詢結(jié)果反饋給用戶，并將這條信息存儲到數(shù)據(jù)表中。 針對數(shù)據(jù)表中存在的污染物，系統(tǒng)會自動提取的化學符號，并按照已經(jīng)建好的平衡二叉樹對其動態(tài)查找，查找到該化學元素后，再根據(jù)用戶輸入的其

9、他查詢條件建立二叉排序樹， 平衡化處理該樹的某些結(jié)點，將其存儲于系統(tǒng)緩沖區(qū)中。 采樣的時間已經(jīng)事先規(guī)定，每隔一定時間都會接受數(shù)據(jù)包，將其自動解析存入數(shù)據(jù)庫后，系統(tǒng)取出所需的數(shù)據(jù)項，插入已經(jīng)建好的二叉樹中，并對其進行刪除操作，去掉冗余的結(jié)點。 當用戶退出操作時，自動對二叉樹進行解構(gòu)，釋放掉其所消耗的所有空間。五、 算法的代碼/*以下是用c+ 實現(xiàn)的二叉排序樹的源代碼*/#include<iostream.h>typedef struct TreeNodeint key;struct TreeNode *left;struct TreeNode *right;treeNode;clas

10、s BiSortTreepublic: BiSortTree(void);void desplayTree(void);/顯示這個樹void insertTree(int key);/在樹中插入一個值 deleteTree(int key);/在樹中刪除一個值 treeNode* searchTree(int key);/在樹中查找一個值BiSortTree();private:treeNode* buildTree(treeNode* head,int number);/建立一個樹treeNode* search(treeNode* head ,int key);/查找treeNode* B

11、iSortTree:searchParent(treeNode* head,treeNode* p);/查找出p的父親節(jié)點的指針treeNode* BiSortTree:searchMinRight(treeNode* head);/找到右子樹中最小的節(jié)點void showTree(treeNode* head);/顯示 void destroyTree(treeNode* head);/刪除treeNode *Head;/*以下是建立一個二叉排序樹*/BiSortTree:BiSortTree() cout<<"建立一棵二叉排序樹,請輸入你要建樹的所有數(shù)(以-1 作為結(jié)

12、束標志!): "<<endl; Head=NULL; int number; cin>>number; while(number!=-1) Head=buildTree(Head,number); cin>>number; treeNode* BiSortTree:buildTree(treeNode* head,int number)treeNode *p; p=new treeNode; p->key=number;p->left =p->right=NULL;if(head=NULL)return p;elseif(p-&g

13、t;key <head->key)head->left=buildTree(head->left,number); else head->right=buildTree(head->right,number); return head;/*以下是在一棵二叉排序樹插入一個數(shù)*/void BiSortTree:insertTree(int key)Head=buildTree(Head,key);/*以下是在一個二叉排序樹查找一個數(shù)是否存在*/treeNode* BiSortTree:searchTree(int key)return search(Head,k

14、ey);treeNode* BiSortTree:search(treeNode* head ,int key) if(head=NULL)return NULL;if(head->key=key)return head;elseif(key<head->key )return search( head->left,key); elsereturn search(head->right,key);/*以下是在一個二叉排序樹刪除一個給定的值*/BiSortTree:deleteTree(int key)treeNode *p;p=NULL; p=search(Hea

15、d,key);if(p=NULL)cout<<"Don't find the key" if(p=Head)Head=NULL;elsetreeNode* parent;parent=searchParent(Head,p);if(p->left=NULL&&p->right=NULL)/葉子節(jié)點 if(parent->left=p)parent->left=NULL; elseparent->right=NULL; else/非葉子節(jié)點 if(p->right=NULL)/該節(jié)點沒有右孩子 if(pa

16、rent->left=p) parent->left=p->left ; else parent->right=p->left; else/該點有左右孩子 treeNode * rightMinSon,* secondParent;/secondParent為右子樹中的最小節(jié)點的父親 rightMinSon=searchMinRight(p->right); secondParent=searchParent(p->right ,rightMinSon); secondParent->left=rightMinSon->right; if(

17、p->right=rightMinSon)/右子樹中的最小節(jié)點的父親為p p->right=rightMinSon->right ; p->key=rightMinSon->key ; treeNode* BiSortTree:searchParent(treeNode* head,treeNode* p)if(head->left=p|head->right=p|head=p|head=NULL)return head; elseif(p->key<head->key)return searchParent(head->lef

18、t ,p);elsereturn searchParent(head->right ,p);treeNode* BiSortTree:searchMinRight(treeNode* head)/找到右子樹中最小的節(jié)點if(head->left =NULL|head=NULL)return head;elsereturn searchMinRight(head->left);/*以下是顯示一個二叉排序樹*/void BiSortTree:desplayTree(void)showTree(Head);cout<<endl;void BiSortTree:showT

19、ree(treeNode* Head)if(Head!=NULL)showTree(Head->left ) ; cout<<Head->key<<' ' ;showTree(Head->right) ;/*以下是刪除一棵整二叉排序樹*/BiSortTree:BiSortTree()cout<<"已經(jīng)消除了一棵樹!"<<endl;destroyTree(Head);void BiSortTree:destroyTree(treeNode* head )if(head!=NULL)destroy

20、Tree(head->left );destroyTree(head->right );delete head;/*/void print() cout<<endl<<endl<<"以下是對二叉排序樹的基本操作:"<<endl<<"1.顯示樹"<<endl<<"2.插入一個節(jié)點"<<endl<<"3.尋找一個節(jié)點"<<endl<<"4.刪除一個節(jié)點"&l

21、t;<endl;void main()BiSortTree tree;int number;int choiceNumber;char flag;while(1) print() ; cout<<"請選擇你要進行的操作(14)"<<endl; cin>>choiceNumber; switch(choiceNumber) case 1: tree.desplayTree();break; case 2: cout<<"請插入一個數(shù): "<<endl; cin>>number;

22、tree.insertTree(number); tree.desplayTree(); break; case 3: cout<<"請插入你要找數(shù): "<<endl; cin>>number; if(tree.searchTree(number)=NULL) cout<<"沒有發(fā)現(xiàn)"<<endl; else cout<<"發(fā)現(xiàn)"<<endl; break; case 4: cout<<"請輸入你要刪除的數(shù): "<

23、<endl; cin>>number; tree.deleteTree(number); tree.desplayTree(); break; default: break; cout<<"你是否要繼續(xù)(Y/N)?"<<endl; cin>>flag; if(flag='N'|flag='n')break;六、 算法在器件注冊碼的搜索算法上的應(yīng)用 單總線上所有器件注冊碼構(gòu)成了一個深度為 64的二叉樹,在遍歷二叉樹的過程中可根據(jù)讀回的數(shù)據(jù)判斷結(jié)點是左子結(jié)點 、右子結(jié)點還是葉子結(jié)點 ,即 :0

24、0表示既存在左子結(jié)點 ,也存在右子結(jié)點 ,該位有 “0”,也有 “1”;01表示只存在左子結(jié)點 ,該位為 “0”; 10表示只存在左子結(jié)點 ,該位為 “1”;11表示不存在子結(jié)點 ,也就說明沒有從器件掛接在總線上 。在遍歷二叉樹時 , 記錄所走的路徑和搜索到的葉子結(jié)點數(shù) ,可以得到從器件的注冊碼和從器件數(shù)量 。第一次搜索從器件的注冊碼時 , 如果左子結(jié)點和右子結(jié)點都存在 ,則需要記錄該分叉結(jié)點的深度 ,并沿左子樹的方向向下搜索 。當搜索深度達到 64時 ,獲得一個從器件的注冊碼 ,并取出該搜索路徑最后的分叉結(jié)點的深度 ,然后主器件執(zhí)行第二次搜索過程 。在該搜索過程中 ,如果結(jié)點的深度值小于最后

25、一個分叉結(jié)點的深度 ,則發(fā)送上次搜索到的在最后一個分叉結(jié)點前的注冊碼的相應(yīng)位 ; 如果結(jié)點的深度值等于最后一個分叉結(jié)點的深度 ,則發(fā)送上次搜索到的在最后一個分叉結(jié)點處發(fā)送的數(shù)據(jù)的反碼 ,并且刪除該分叉結(jié)點的記錄 ; 如在后面的搜索中遇到分叉結(jié)點 ,同樣需要記錄分叉結(jié)點的深度 。這樣 ,每搜索到一個深度為 64的葉子結(jié)點 ,就會得到一個從器件的注冊碼 ,一直搜索到記錄中沒有分叉結(jié)點為止 。設(shè)有 3個從器件 1、2和 3,主設(shè)備第一次讀取的數(shù)據(jù)是 “10”,可知從器件注冊碼的第一位都為 “0”,主設(shè)備寫 “0”; 第二次讀取的數(shù)據(jù)是“00”,可知在線從器件的注冊碼在該位既有 “0”,也有 “1”,記下該分叉結(jié)點的深