程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 二叉排序樹(二叉查找樹)的基本操作

二叉排序樹(二叉查找樹)的基本操作

編輯:C++入門知識

二叉排序樹(二叉查找樹)的基本操作


二叉排序樹的查找屬於動態查找的范疇,根據查找過程中是否對表進行修改,可以把查找分為靜態查找和動態查找。動態查找表的特點是:表結構本身是在查找過程中動態生成的,即對於給定的key值,若表中存在其關鍵字等於key的記錄,則查找成功並返回,否則插入關鍵字等於key的記錄。

二叉排序樹或者是一顆空樹,或者是具有下列性質的二叉樹:

(1)若它的左子樹非空,則左子樹上的所有結點的值均小於根節點的值;

(2)若它的右子樹非空,則右子樹上的所有結點的值均大於根節點的值;

(3)它的左右子樹也分別為二叉排序樹;


1、二叉排序樹的數據結構

typedef struct node
{
	short key;
	struct node *rchild,*lchild;
} BSTNode,*BSTree;

2、二叉排序樹的插入和生成

已知一個關鍵字值為key的節點s,若將其插入到二叉排序樹中,只要保證插入後仍符合二叉排序樹的定義即可,插入可以用一下方法。

(1)若二叉排序樹為空樹,則key稱為二叉排序樹的根;
(2)若二叉排序樹非空,則將key與二叉排序樹的根比較,如果key值等於根節點,則停止插入;如果key值小於根節點的值,則將key插入左子樹;如果key值大於根節點的值,則將key插入右子樹;

二叉樹的插入算法如下:

void InsertBST(BSTree* bst,short key)
{
    BSTree s;
    if(*bst==NULL)    //遞歸結束條件;該結點為空時創建結點;
    {
        s=(BSTree)malloc(sizeof(BSTNode));
        s->key=key;
        s->lchild=NULL;
        s->rchild=NULL;
        *bst=s;
    }
    else if(key<(*bst)->key)
    {
        InsertBST(&((*bst)->lchild),key);
    }
    else if(key>(*bst)->key)
    {
        InsertBST(&((*bst)->rchild),key);
    }
}

/******************
* 根據二叉排序樹的插入算法可以創建一顆二叉排序樹;
****************************/
void CreateBST(BSTree* bst)
{
    char key;
    *bst=NULL;
    scanf("%c",&key);
    while (key!='?')          //輸入字符的結束是'?';
    {
        InsertBST(bst,key);
        scanf("%c",&key);
    }
}

3、二叉排序樹的刪除

在二叉排序樹中刪除一個結點比插入一個結點要困難,除非是葉子結點,否則必須考慮部分鏈的對接,以保證刪除一個結點後能使剩下的結點仍是一顆二叉排序樹。

假設要刪除的結點為P,其雙親結點為F,且不失一般性,並設結點P是結點F的左孩子(右孩子情況類似)。如下圖所示:(注:下圖截至數據結構書中)。\

下面分三種情況進行討論:

(1)若P為葉子節點,刪除P後只需修改雙親節點的指針即可;
(2)如果P的左子樹為空或者P的右子樹為空,此時只需令其左右子樹PL,PR成為其雙親結點F的左右子樹即可;

(3)若P的左右子樹均不為空,如圖8.7(a)所示:此時有兩種處理方法。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+ICC3vbeoMaO6ytfPyNXStb1QveG149Ta1tDQ8tDywdDW0LXE1rG908ewx/1TveG146OsyOfNvDguN6OoYqOpy/nKvqOsyLu6872rULXE1/PX08r3uMTOqka1xNfz19PK96OsULXE09LX08r3uMTOqlO1xNPS19PK96O7PC9wPgo8cD4gIEYtPmxjaGlsZD1QLT5sY2hpbGQ7Uy0+cmNoaWxkPVAtPnJjaGlsZDtmcmVlKFApO73hufvI5828OC43o6hjo6nL+cq+o7rS8s6qULXE09K94bXjyv0mIzIwNTQwO7HIU7XEyv0mIzIwNTQwO7Tzo6y5yrK7u+G4xLHktv6y5sXF0PLK97XE0NTWyjs8L3A+CjxwPiC3vbeoMqO6ytfPyNXStb1QveG149Ta1tDQ8tDywdDW0LXE1rG908ewx/1TveG146OsyOfNvDguN6OoYqOpy/nKvqOsyLu689PDU73hteO1xCYjMjA1NDA7tPrM5lC94bXjtcQmIzIwNTQwO6Os1Nm9q1O94bXjyb6z/SzUrVO94bXjtcTX89fTyve4xM6qy6vH1zwvcD4KPHA+IL3hteNRveG147XE09LX08r3o7tQLT5kYXRhPVMtPmRhdGE7US0+cmNoaWxkPVMtPmxjaGlsZDtmcmVlKFMpoaO94bn7yOfNvDguN6OoZKOpy/nKvqGjPC9wPgo8cD6+38zly+O3qMPoyvbI58/Co7o8L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">void DelBST(BSTree *t,short key) { BSTNode *p,*f,*s,*q; p=*t; f=NULL; while (p) //查找關鍵字為key的待刪節點; { if(p->key==key) { break; } f=p; //f指向p節點的雙親節點; if(p->key>key) { p=p->lchild; } else { p=p->rchild; } } if(p==NULL) //如果沒有找到直接返回; { return; } if(f==NULL) //如果p是原二叉排序樹的根; { free(p); *t=NULL; return; } if(p->lchild==NULL&&p->rchild==NULL) //如果p沒有左右子樹; { if(f->lchild==p) { f->lchild=NULL; } else { f->rchild=NULL; } free(p); } else if(p->lchild==NULL&&p->rchild!=NULL) //如果p的左子樹為空,右子樹不為空; { if(f->lchild==p) { f->lchild=p->rchild; //把p的右子樹鏈接到父親的左鏈上; } else { f->rchild=p->rchild; //把p的右子樹鏈接到父親的右鏈上; } free(p); } else if(p->lchild!=NULL&&p->rchild==NULL) //如果p的左子樹不為空,右子樹為空; { if(f->lchild==p) { f->lchild=p->lchild; //把p的右子樹鏈接到父親的左鏈上; } else { f->rchild=p->lchild; //把p的右子樹鏈接到父親的右鏈上; } free(p); } else if(p->lchild!=NULL&&p->rchild!=NULL) //如果p的左右子樹都不為空; { q=p; s=p->lchild; //s指向p的左節點; while (s->rchild) { q=s; s=s->rchild; } p->key=s->key; //把s節點的數據賦值給p節點; if(p==q) //說明待刪除的p節點的左子節點下沒有右結點; { q->lchild=s->lchild; //把s節點的左子樹鏈接到q的左節點下; } else { q->rchild=s->lchild; //把s節點的左子樹鏈接到q的右節點下; } free(s); } }
4.二叉排序樹的查找

由二叉排序樹的定義可知,在二叉排序樹上進行查找與二分查找類似。即:當二叉排序樹不為空時,首先將給定值與根結點的關鍵值相比較,若相等,則查找成功。否則,將依據給定值和根節點關鍵值之間的大小關系,分別在左右子樹上繼續進行查找,其查找過程的算法如下:

BSTree SearchBST(BSTree bst,short key)
{
	if(bst==NULL)
	{
		return NULL;
	}
	if(bst->key==key)
	{
		return bst;
	}
	else if(bst->key>key)
	{
		return SearchBST(bst->lchild,key);
	}
	else 
	{
		return SearchBST(bst->rchild,key);
	}
}

5、二叉排序樹的查找分析

根據二叉排序樹的查找算法可以看出,二叉排序樹的查找和二分查找類似,和關鍵字比較次數不超過樹的深度,然而二分查找長度n的表判定樹是唯一的,而含有n個結點二叉排序樹卻不唯一。對於含有同樣關鍵字序列的一組結點,結點插入的先後次序不同,所構成的二叉排序樹的形態和深度不同。而二叉排序樹的平均查找長度ASL與二叉樹的形態相關,二叉排序樹的各分支越均衡,樹的深度越淺,其平均查找長度ASL越小。

就平均性能而言,二叉排序樹上的查找和二分查找相差不大,並且二叉排序樹上的插入和刪除結點十分方便,無需移動大量的結點。因此,對於需要經常做插入、刪除、查找運算的表,宜采用二叉排序樹,因此二叉排序樹又稱為二叉查找樹。

6、總結

上面是我在精讀數據結構時,對二叉排序樹的一點總結,也參考了相關的書籍,望各位讀者多多指教。
























  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved