《數(shù)據(jù)結(jié)構(gòu)A》第07章

《《數(shù)據(jù)結(jié)構(gòu)A》第07章》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)DataStructuresinC++南京郵電大學計算機學院陳慧南2006年9月第7章動態(tài)集和搜索樹南京郵電大學計算機學院陳慧南2006年9月7.1??二叉搜索樹7.2??二叉平衡樹7.3B-樹南京郵電大學計算機學院陳慧南2006年9月7.1二叉搜索樹南京郵電大學計算機學院陳慧南2006年9月7.1.1二叉搜索樹的定義定義7.1設(shè)結(jié)點由關(guān)鍵字值表征，假定所有結(jié)點的關(guān)鍵字值各不相同，二叉搜索樹或者是一棵空二叉樹，或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結(jié)點的關(guān)鍵字值均小于根結(jié)點的關(guān)鍵字值；（2）若右子樹不空，則右子樹上所有結(jié)點的關(guān)鍵字值

2、均大于根結(jié)點的關(guān)鍵字值；（3）左、右子樹也分別是二叉搜索樹。南京郵電大學計算機學院陳慧南2006年9月性質(zhì)7.1若以中序遍歷一棵二叉搜索樹，將得到一個以關(guān)鍵字值遞增排列的有序序列。南京郵電大學計算機學院陳慧南2006年9月二叉搜索樹類templateclassBSTree:publicDynamicSet{public:BSTree(){root=NULL;}ResultCodeSearch(T&x)const;ResultCodeInsert(T&x);ResultCodeRemove(T&x);?protected:BTNode*r

3、oot;private:ResultCodeSearch(BTNode*p,T&x)const;?};南京郵電大學計算機學院陳慧南2006年9月7.1.2二叉搜索樹的搜索二叉搜索樹搜索遞歸算法templateResultCodeBSTree::Search(T&x)const{returnSearch(root,x);}南京郵電大學計算機學院陳慧南2006年9月templateResultCodeBSTree::Search(BTNode*p,T&x)const{if(!p)returnNotPresent;

4、elseif(xelement)returnSearch(p->lChild,x);elseif(x>p->element)returnSearch(p->rChild,x);else{x=p->element;returnSuccess;}}南京郵電大學計算機學院陳慧南2006年9月二叉搜索樹搜索迭代算法templateResultCodeBSTree::Search(T&x)const{BTNode*p=root;while(p)if(xelement)p=p->lChild;elseif(x>p->element)

5、p=p->rChild;else{x=p->element;returnSuccess;}returnNotPresent;}南京郵電大學計算機學院陳慧南2006年9月7.1.3二叉搜索樹的插入templateResultCodeBSTree::Insert(T&x){BTNode*p=root,*q=NULL;while(p){q=p;if(xelement)p=p->lChild;elseif(x>p->element)p=p->rChild;else{x=p->element;returnDuplicate;}}南京郵電大

6、學計算機學院陳慧南2006年9月p=newBTNode(x);if(!root)root=p;elseif(xelement)q->lChild=p;elseq->rChild=p;returnSuccess;}南京郵電大學計算機學院陳慧南2006年9月南京郵電大學計算機學院陳慧南2006年9月7.1.4二叉搜索樹的刪除若結(jié)點*p有兩棵非空子樹需搜索*p的中序遍歷次序下的直接后繼（或直接前驅(qū)）結(jié)點，設(shè)為*s，將*s的值復制到*p中，稱為替代，因為*s最多只有一棵非空子樹，這樣一來，問題轉(zhuǎn)化為“被刪除的結(jié)點最多只有一棵非空子樹”的情形。南京郵電大學計算

7、機學院陳慧南2006年9月若結(jié)點*p只有一棵非空子樹或*p是葉子以*p的惟一孩子（設(shè)為*c）或空子樹（c＝NULL）取代*p，鏈接至*p的雙親結(jié)點*q。若被刪除的結(jié)點*p是根結(jié)點，則刪除后，結(jié)點*c成為新的根；若*p是其雙親*q的左孩子，則*c也應成為*q的左孩子，否則*c成為*q的右孩子。最后釋放結(jié)點*p所占用的空間。南京郵電大學計算機學院陳慧南2006年9月刪除28南京郵電大學計算機學院陳慧南2006年9月南京郵電大學計算機學院陳慧南2006年9月templateResultCodeBSTree::Remove(T&x){BTNode

8、>*c,*