第六章二叉樹的應用

第六章

二叉樹的應用二叉搜索樹堆

哈夫曼6.1二叉搜索樹6.1.1二叉搜索樹的定義1．定義2．查找算法3．插入算法4．刪除算法5．查找性能的分析6.1.1二叉搜索樹的定義二叉搜索樹(BinanySearchingTree)又稱二叉排序樹(BinarySortingTree)或者是一棵空樹；或者是具有如下特性的二叉樹：（1）若它的左子樹不空，則左子樹上所有結點的關鍵字均小于根結點的關鍵字；（2）若它的右子樹不空，則右子樹上所有結點的關鍵字均大于根結點的關鍵字；（3）它的左、右子樹本身分別是一棵二叉搜索樹。503080209010854035252388是二叉搜索樹。66不通常，取二叉鏈表作為二叉排序樹的存儲結構

structBTreeNode

{ElemTypedata;

BTreeNode

*left;

BTreeNode

*right;};6.1.3二叉搜索樹的運算

1.查找

若二叉排序樹為空，則查找

不成功；否則，若給定值1）等于根結點的關鍵字，則查找成功；2）小于根結點的關鍵字，則繼續(xù)在左子樹上查找；3）大于根結點的關鍵字，則繼續(xù)在右子樹上查找。50308020908540358832查找關鍵字==50,505035

,503040355090,50809095

boolFind(BTreeNode*T,

ElemType&item)

if(T==NULL)returnfalse;//查找失敗

else{if(item==T->data)

{item=T->data;returntrue;} elseif(item<T->data)

//向左子樹繼續(xù)查找

returnFind(T->left,item);

else returnFind(T->right,item);}

//向右子樹繼續(xù)查找30201040352523T設

key=48TT23TTTT

boolFind(BTreeNode*T,

ElemType&item)

if(T==NULL)returnfalse;//查找失敗

else{if(item==T->data)

{item=T->data;returntrue;} elseif(item<T->data)

//向左子樹繼續(xù)查找

returnFind(T->left,item);

else returnFind(T->right,item);}

//向右子樹繼續(xù)查找

boolFind(BTreeNode*T,

ElemType&item)

while(T!=NULL)

{if(item==T->data)

{item=T->data;returntrue;} elseif(item<T->data)

T=T->left;//向左子樹繼續(xù)查找

else T=T->right;

//向右子樹繼續(xù)查找

returnfalse;}

“插入”操作在查找不成功時才進行；3．二叉搜索樹的插入算法若二叉搜索樹為空樹，則新插入的結點為根結點；否則，新插入的結點必為一個葉子結點，其插入位置由查找過程得到。28503826629435依次插入:(38，26，62，94，35，50，28，55)50二叉搜索樹的插入算法（1）被刪除的結點是葉子；（2）被刪除的結點只有左子樹

或者只有右子樹；（3）被刪除的結點既有左子樹，也有右子樹。4．二叉搜索樹的刪除算法可分三種情況討論：50308020908540358832（1）被刪除的結點是葉子結點被刪關鍵字=2088其雙親結點相應指針域改為“空”50308020908540358832（2）被刪除的結點只有單支子樹其雙親結點的相應指針域改為

“指向被刪除結點的左子樹或右子樹”。被刪關鍵字=4080p

右子樹為空只需重接它的左子樹q=p;p=p->lchild;delete(q);pp左子樹為空只需重接它的右子樹q=p;p=p->rchild;delete(q);p50308020908540358832（3）被刪除的結點有左右子樹4040被刪結點前驅(qū)結點被刪關鍵字=50以其前驅(qū)替代之，然后再刪除該前驅(qū)結點503080209085403588325050503040355050809045如何查找前驅(qū)左子樹中“最右下”的結點（左指針可能不為空）q=p;s=p->lchild;while(!s->rchild){q=s;s=s->rchild;}

//s

指向被刪結點的前驅(qū)p503080209085403588325050503040355050809045找到前驅(qū)s

p->data=s->data;q->rchild=s->lchild;

sqpq=p;s=p->lchild;while(!s->rchild){q=s;s=s->rchild;}

//s

指向被刪結點的前驅(qū)//左右子樹均不空,刪除P

所指結點p->data=s->data;if(q!=p)q->rchild=s->lchild;

elseq->lchild=s->lchild;

//重接*q的左子樹delete(s);pqs50308020908540358832（3）被刪除的結點有左右子樹60被刪關鍵字=50以其后繼替代之，然后再刪除后繼結點60關鍵字序列3，1，2，5，4構造的二叉排序樹，由關鍵字序列

1，2，3，4，5構造的二叉排序樹，2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.26.2堆

6.2.1堆的定義堆(Heap)

是具有如下特性的一棵

完全二叉樹：(1)若根結點存在左(右)孩子，則根結點的值小于等于(大于等于)左(右)孩子結點的值；(2)以左、右孩子為根的子樹又各是一個堆。

堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或12,36,27,65,40,34,98,81,73,55,49是小頂堆12,36,27,65,40,14,98,81,73,55,49不是堆(小頂堆)(大頂堆)rir2ir2i+1對于完全二叉樹r2i

是ri

的左孩子r2i+1

是ri

的右孩子1236276549817355403498是堆14不堆的抽象數(shù)據(jù)類型：

void

InitHeap(HeapType&HBT);voidClearHeap(HeapType&HBT);

boolHeapEmpty

(HeapType&HBT);voidInsertHeap

(HeapType&HBT,constElemTypeitem);

ElemTypeDeleteHeap

(HeapType&HBT);

struct

Heap

{

ElemType

heap[HeapMaxSize];

int

size;};

//HeapMaxSize為已經(jīng)事先定義的全局常量堆的順序存儲類型如何“建堆”？兩個問題:如何“篩選”？完全二叉樹

調(diào)整為堆“篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結點使整個二叉樹也成為一個堆。堆堆篩選是大頂堆988149735564123627401298128173641298比較比較篩選405549738164361227981236817349988173559849406436122740,55,49,73,12,27,98,81,64,36建堆是一個從下往上進行“篩選”的過程。0123456789182635734860

182673356048向堆中插入一個元素30303035

void

InsertHeap(Heap&T,ElemTypeitem){T.heap[T.size]=item;

T.size++;//向堆尾添加新元素

ElemTypex=item;//將新元素暫存x中

inti=T.size-1;

//用i指向待調(diào)元素位置

while(i!=0){ intj=(i-1)/2;

//j指向i元素的雙親

if(x>=T.heap[j])break;

//調(diào)整結束

T.heap[i]=T.heap[j];

//雙親下移

i=j;}//調(diào)整元素改為雙親

T.heap[i]=x;}//把新元素調(diào)到最終位置從堆頂刪除一個元素497364271236815598402798814972362740556412121298

ElemTypeDeleteHeap(Heap&HBT){if(HBT.size==0){ cerr<<"Heapnull!"<<endl; exit(1);}

//空堆

ElemTypetemp=HBT.heap[0]; HBT.size--;//取出堆頂元素

if(HBT.size==0)returntemp;

//只有一個根元素

ElemTypex=HBT.heap[HBT.size];

//將待調(diào)整的堆尾元素暫存x中，//以便放入最終位置

inti=0;intj=2*i+1;

while(j<=HBT.size-1)

{

if(j<HBT.size-1&&

HBT.heap[j]>HBT.heap[j+1])

j++;

if(x<=HBT.heap[j])break;

HBT.heap[i]=HBT.heap[j];

i=j;j=2*i+1;

}HBT.heap[i]=x;

returntemp;}6.3哈夫曼樹最優(yōu)樹的定義如何構造最優(yōu)樹

若在一棵樹中存在著一個結點序列k1,k2,…,kj，使得ki是ki+1的雙親(1≤i<j)，則稱此結點序列是從k1到kj的路徑從k1到kj所經(jīng)過的分支數(shù)稱為這兩點之間的路徑長度

6.3.1基本術語

路徑和路徑長度

給結點賦上一個有某種意義的實數(shù)，我們稱為權。帶權路徑長度

從根結點到該結點之間路徑長度與該結點上權的乘積。

結點的權和帶權路徑長度權

樹的帶權路徑長度

樹中所有葉子結點的帶權路徑長度之和