- 註冊時間
- 2006-10-8
- 最後登錄
- 2019-6-20
- 主題
- 查看
- 積分
- 1306
- 閱讀權限
- 110
- 文章
- 1393
- 相冊
- 0
- 日誌
- 1
  
狀態︰
離線 
|
二元排序樹的查找演算法
在二元排序樹b中查找x的過程為：
1.若b是空樹，則搜索失敗，否則：
2.若x等於b的根節點的數據域之值，則查找成功；否則：
3.若x小於b的根節點的數據域之值，則搜索左子樹；否則：
4.查找右子樹。
/* 以下代码为C++写成, 下同 */
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){
//在根指针T所指二元排序樹中递归地查找其關键字等於key的數據元素，若查找成功，
//則指针p指向該數據元素節點，并返回TRUE，否則指针指向查找路徑上訪問的最後
//一個節點并返回FALSE，指针f指向T的雙親，其初始调用值為NULL
if(!T) { //查找不成功
p=f;
return false;
}
else if (key == T->data.key) { //查找成功
p=T;
return true;
}
else if (key < T->data.key) //在左子樹中繼續查找
return SearchBST(T->lchild, key, T, p);
else //在右子樹中繼續查找
return SearchBST(T->rchild, key, T, p);
}
[编辑] 在二叉排序樹插入結點的演算法向一個二叉排序樹b中插入一個結點s的演算法，過程為：
1.若b是空樹，則將s所指結點作為根結點插入，否則：
2.若s->data等於b的根結點的數據域之值，則返回，否則：
3.若s->data小於b的根結點的數據域之值，則把s所指結點插入到左子樹中，否則：
4.把s所指結點插入到右子樹中
/*当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，否则返回FALSE*/
Status InsertBST(BiTree &T, ElemType e){
if(!SearchBST(T, e.key, NULL,p){
s = new BiTNode;
s->data = e; s->lchild = s->rchild = NULL;
if(!p)
T=s; //被插结点*s为新的根结点
else if (e.key < p->data.key)
p->lchld = s; //被子插结点*s为左孩子
else
p->rchild = s; //被插结点*s为右孩子
return true;
}
else
return false; //树中已有关键字相同的结点，不再插入
}
}
在二叉排序樹刪除結點的演算法
在二叉排序樹刪去一個結點，分三種情況討論：
1.若*p結點為葉子結點，即PL(左子樹)和PR(右子樹)均為空樹。由於刪去葉子結點不破壞整棵樹的結構，則只需修改其雙親結點的指針即可。
2.若*p結點只有左子樹PL或右子樹PR，此時只要令PL或PR直接成為其雙親結點*f的左子樹（當*p是左子樹）或右子樹（當*p是右子樹）即可，作此修改也不破壞二叉排序樹的特性。
3.若*p結點的左子樹和右子樹均不空。在刪去*p之後，為保持其它元素之間的相對位置不變，可按中序遍歷保持有序進行調整，可以有兩種做法：其一是令*p的左子樹為*f的左子樹，*s為*f左子樹的最右下的結點，而*p的右子樹為*s的右子樹；其二是令*p的直接前驅（或直接後繼）替代*p，然後再從二叉排序樹中刪去它的直接前驅（或直接後繼）。在二叉排序樹上刪除一個結點的演算法如下：
Status DeleteBST(BiTree &T, KeyType key){
//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素，并返回
//TRUE；否则返回FALSE
if(!T)
return false; //不存在关键字等于key的数据元素
else{
if(key == T->data.key) { // 找到关键字等于key的数据元素
return Delete(T);
}
else if(key < T->data.key)
return DeleteBST(T->lchild, key);
else
return DeleteBST(T->rchild, key);
}
}
Status Delete(BiTree &p){
//从二叉排序树中删除结点p，并重接它的左或右子树
if(!p->rchild){ //右子树空则只需重接它的左子树
q=p;
p=p->lchild;
delete q;
}
else if(!p->lchild){ //左子树空只需重接它的右子树
q=p;
p=p->rchild;
delete q;
}
else{ //左右子树均不空
q=p;
s=p->lchild;
while(s->rchild){
q=s;
s=s->rchild;
} //转左，然后向右到尽头
p->data = s->data; //s指向被删结点的“前驱”
if(q!=p)
q->rchild = s->lchild; //重接*q的右子树
else
q->lchild = s->lchild; //重接*q的左子树
delete s;
}
return true;
}
二叉排序樹性能分析
每個結點的為該結點的層次數。最壞情況下，當先後插入的關鍵字有序時，構成的二叉排序樹蛻變為單支樹，樹的深度為，其平均查找長度為（和順序查找相同），最好的情況是二叉排序樹的形態和折半查找的判定樹相同，其平均查找長度和成正比（）。
二叉排序樹的優化
請參見主條目平衡樹。
1.Size Balanced Tree(SBT)
2.AVL樹
3.紅黑樹
4.Treap(Tree+Heap)
這些均可以使查找樹的高度為
計算機科學中的樹
二元樹 二元樹 · 二元搜尋樹 (BST) · 笛卡爾樹 · Top tree · T樹
自平衡二元搜尋樹 AA樹 · AVL樹 · 紅黑樹 · 伸展樹 · 樹堆 · 節點大小平衡樹
B樹 B樹 · B+樹 · B*樹 · Bx樹 · UB樹 · 2-3樹 · 2-3-4樹 · (a,b)-樹 · Dancing tree · H樹
Trie 前綴樹 · 後綴樹 · 基數樹
空間劃分樹 四叉樹 · 八叉樹 · k-d樹 · vp-樹 · R樹 · R*樹 · R+樹 · X樹 · M樹 · 線段樹 · 希爾伯特R樹 · 優先R樹
非二元樹 Exponential tree · Fusion tree · 區間樹 · PQ tree · Range tree · SPQR tree · Van Emde Boas tree
其他類型 堆 · 散列樹 · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree · 樹狀數組
|
-
總評分: 威望 + 2
查看全部評分
|
發表於 2012-6-6 10:33:34
發表於 2012-6-6 23:15:55
