數(shù)據(jù)結(jié)構(gòu)---二叉排序樹

1、數(shù)據(jù)結(jié)構(gòu)-叉排序樹二叉排序樹(Bi nary Sort Tree)又稱二叉查找樹，亦稱二叉搜索樹。它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：(1) 若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；(2) 若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；(3) 左、右子樹也分別為二叉排序樹；一、查找：步驟：若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查左子樹。若大于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查右子樹。若子樹為空，查找不成功。平均情況分析(在成功查找兩種的情況下)：在一般情況下，設(shè)P (n, i )且它的左子樹的結(jié)點(diǎn)個(gè)數(shù)為i時(shí)的平均查找 長(zhǎng)度。如

2、圖的結(jié)點(diǎn)個(gè)數(shù)為 n = 6且i = 3;則P (n,i )二P(6, 3)= 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 / 6= 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 / 6注意：這里P(3)、P(2)是具有3個(gè)結(jié)點(diǎn)、2個(gè)結(jié)點(diǎn)的二叉分類樹的平均 查找長(zhǎng)度。在一般情況，P( i )為具有i個(gè)結(jié)點(diǎn)二叉分類樹的平均查找長(zhǎng)度。P(3) =( 1+2+2) / 3 = 5/3P(2) =( 1+2) / 2 = 3/2 P (n,i ) = 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) / n

3、«-1P (n) = P (n,i ) / n <= 2(1+l/n)lnn因?yàn)?2(1+I/n)lnn 1.38logn 故 P(n)=O(logn)二、插入刪除與次優(yōu)二叉樹相對(duì)，二叉排序 樹是一種動(dòng)態(tài)樹表。其特點(diǎn)是：樹 的結(jié)構(gòu)通常不是一次生成的，而是 在查找過程中，當(dāng)樹中不存在關(guān)鍵 字等于給定值的節(jié)點(diǎn)時(shí)再進(jìn)行插 入。新插入的結(jié)點(diǎn)- 定是一 -個(gè)新添 加的葉子節(jié)點(diǎn)，并且是查找不成功 時(shí)查找路徑上訪問的最后一個(gè)結(jié)點(diǎn) 的左孩子或右孩子結(jié)點(diǎn)。三、插入算法首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入 若二叉樹為空。則首先單

4、獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。void InsertBST(t , key)if(t=NULL)t=newBiTree;t->lchild=t->rchild=NULL;t->data=key;return;if(key<t->data )In sertBST(t->lchild,key);elseIn sertBST (t->rchild, key );n個(gè)數(shù)據(jù)在數(shù)組d中，tree為二叉排序樹根void CreateBiTree(tree,d , n)tree=NULL;for(i=0;i< n;i+)In sertBST(tr

5、ee,di);最小值二叉樹c例程：#i nclude<stdio.h>struct priorityqueueintcapacity;intsize;structpriorityqueue *eleme nts;*tryit;structpriorityqueue *in itialize ( intmaxeleme nts )structpriorityqueue *h;h = malloc( sizeof ( struct priorityqueue );h -> eleme nts = malloc( sizeof ( int ) * ( maxeleme nts+ 1

6、 );h -> capacity = maxeleme nts;h -> size = 0;h -> eleme nts0 = -23767;returnh;void in sert ( intx , struct priorityqueue *h )int i;for ( i = +h -> size ; h -> eleme nts i / 2 > x ; i/= 2 )h -> elements i = h -> elements i / 2 ;h -> eleme nts i = x;int deletem in ( structp

7、riorityqueue *h )int i , child ;intmin eleme nt , lasteleme nt;min eleme nt = h -> eleme nts 1 ;lastelement = h -> elements h -> size-;for ( i = 1 ; i * 2 <= h -> size ; i = child )child = i * 2;if( child != h -> size && h -> elements child< h -> eleme nts child )c

8、hild+;if( lasteleme nt > h -> eleme nts child )h -> elements i = h -> elements child ;elsebreak;h -> elements i = lastelement;returnmin eleme nt;mai n()tryit = in itialize ( 10 );in sert ( 4 , tryit );in sert ( 5 , tryit );in sert ( 10 , tryit );in sert ( 3 , tryit );printf("%dn&

9、quot;,deletemin (tryit );printf("%dn",deletemin (tryit );printf("%dn",deletemin (tryit );printf("%dn",deletemin (tryit );getch();四、刪除結(jié)點(diǎn)在二二叉排序樹刪去一個(gè)結(jié)點(diǎn)，分三種情況討論：1.若*p結(jié)點(diǎn)為葉子結(jié)點(diǎn)，即PL（左子樹）和PR佑子樹）均為空樹。由于刪去葉子結(jié)點(diǎn)不破壞整棵樹的結(jié)構(gòu)，則只需修改其雙親結(jié)點(diǎn)的指針即可2. 若*p結(jié)點(diǎn)只有左子樹PL或右子樹PR此時(shí)只要令PL或PR直接成為其 雙親結(jié)點(diǎn)*f的左子樹

10、（當(dāng)*p是左子樹）或右子樹（當(dāng)*p是右子樹）即可, 作此修改也不破壞二叉排序樹的特性。3. 若*p結(jié)點(diǎn)的左子樹和右子樹均不空。在刪去*p之后，為保持其它元素之 間的相對(duì)位置不變，可按中序遍歷保持有序進(jìn)行調(diào)整，可以有兩種做法：其一是令*p的左子樹為*f的左/右（依*p是*f的左子樹還是右子樹而定） 子樹，*s為*p左子樹的最右下的結(jié)點(diǎn)，而*p的右子樹為*s的右子樹； 其二是令*p的直接前驅(qū)（或直接后繼）替代*p，然后再?gòu)亩媾判驑渲?刪去它的直接前驅(qū)（或直接后繼）一即讓 *f的左子樹（如果有的話）成為 *p左子樹的最左下結(jié)點(diǎn)（如果有的話），再讓*f成為*p的左右結(jié)點(diǎn)的父結(jié) 點(diǎn)。在二叉排序樹上刪除

11、一個(gè)結(jié)點(diǎn)的算法如下：#defi ne Status boolStatus Delete(BiTree*); /必須先申明Status DeleteBST(BiTree &T, KeyType key)/若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，則刪除該數(shù)據(jù)元素， 并返回/TRUE ;否貝U返回 FALSEif(!T)return false; /不存在關(guān)鍵字等于key的數(shù)據(jù)元素elseif(key = T->data.key) /找到關(guān)鍵字等于 key的數(shù)據(jù)元素returnDelete(T);else if(key < T->data.key)returnDe

12、leteBST(T->lchild, key);elsereturnDeleteBST(T->rchild, key);ture;returnStatus Delete(BiTree & p)/從二叉排序樹中刪除結(jié)點(diǎn)p,并重接它的左或右子樹if(!p->rchild) /右子樹空則只需重接它的左子樹q=p; p=p->lchild; deleteq;else if(!p->lchild) /左子樹空只需重接它的右子樹q=p;p=p->rchild; deleteq;else /左右子樹均不空q=p; s=p->lchild; while(s->rchild)q=s; s=s->rchild; /轉(zhuǎn)左，然后向右到盡頭p->data = s->data; /s指向被刪結(jié)點(diǎn)的前驅(qū)”if(q!=p)q->rchild = s->lchild; /重接*q的右子樹elseq