# 一、概念
### 1.定義與性質
(1)設x為二叉查找樹中的一個結點,若y是x左子樹中的一個結點,則key[y] <= key[x];若y是x右子樹中的一個結點,則key[x]<=key[y]
(2)二叉查找樹上執行的基本操作的時間與樹的高度成正比。
### 2.結構
(1)結點結構:
關鍵字key
衛星數據data
分別指向父、左右孩子的指針p, left, right
### 3.在二叉查找樹上的操作
查找一個關鍵字:SEARCH(x, k)
求最小關鍵字:MINIMUM(x)
求最大關鍵字:MAXIMUM(x)
求前驅:PREDECESSOR(x)
求后繼:SUCCESSOR(x)
插入一個結點:INSERT(T, z)
刪除一個結點:DELETE(z)
### 4.二叉查找樹的應用
1.遍歷:中序遍歷、先序遍歷、后序遍歷
2.查找:查找包含某個關鍵字的結點,查找關鍵字最大或最小的結點、查找某個結點的前驅或后繼
# 二、代碼
[頭文件](https://code.csdn.net/mishifangxiangdefeng/algoritmcollection/tree/master/include/binarySearchTree.h)
[產品代碼](https://code.csdn.net/mishifangxiangdefeng/algoritmcollection/tree/master/src/binarySearchTree.cpp)
測試代碼
# 三、練習
### 12.1 二叉查找樹
12.1-2
二叉查找樹:左子樹關鍵字<根結點關鍵字<右子樹關鍵字
堆:左子樹關鍵字<根結點關鍵字 && 右子樹關鍵字<根結點關鍵字
不能,因為一個結點的的左子樹與右子樹的關鍵字大小沒有關系
12.1-3
用棧實現:見[算法導論-10.4-有根樹的表示](http://blog.csdn.net/mishifangxiangdefeng/article/details/7707756)中的10.4-3
不用棧實現:見[算法導論-10.4-5](http://blog.csdn.net/mishifangxiangdefeng/article/details/7708490)
12.1-4
~~~
//遞歸的先序遍歷
void BST_Tree::Preorder_Tree_Walk(BST_Node *x)
{
//x不是葉子結點
if(x != NULL)
{
//訪問當前結點
cout<<x->key<<' ';
//先序遍歷當前結點的左子樹
Preorder_Tree_Walk(x->left);
//先序遍歷當前結點的右子樹
Preorder_Tree_Walk(x->right);
}
}
//遞歸的后序遍歷
void BST_Tree::Postorder_Tree_Walk(BST_Node *x)
{
//x不是葉子結點
if(x != NULL)
{
//后序遍歷當前結點的左子樹
Postorder_Tree_Walk(x->left);
//后序遍歷當前結點的右子樹
Postorder_Tree_Walk(x->right);
//訪問當前結點
cout<<x->data<<' ';
}
}
~~~
### 12.2 查詢二叉查找樹
~~~
12.2-1
c,e
12.2-2
//遞歸地查找最小值
BST_Node *BST_Tree::Tree_Minimum(BST_Node *x)
{
if(x->left != NULL)
return Tree_Minimum(x->left);
else return x;
}
//遞歸的查找最大值
BST_Node *BST_Tree::Tree_Maximum(BST_Node *x)
{
if(x->right != NULL)
return Tree_Maximum(x->right);
else return x;
}
12.2-3
//查找中序遍歷下x的前驅,即小于x的最大值
BST_Node *BST_Tree::Tree_Predecessor(BST_Node *x)
{
//如果x的左子樹非空
if(x->left != NULL)
//x的前驅是x的左子樹的最大值
return Tree_Maximum(x->left);
//如果x的左子樹為空且x有前驅y,那么y是x的最低祖先結點,且y的右兒子也是
BST_Node *y = x->p;
while(y != NULL && x == y->left)
{
x = y;
y = y->p;
}
return y;
}
12.2-4
(1)
4->left = 2 4->right =NIL
2->left = 1 2->right = 3
搜索路徑4-2-1
(2)
1->right = 3 1->left = NUL
3->left = 2 3->right = 4
搜索路徑1-3-4
~~~
### 12.3 插入和刪除
12.3-1
~~~
//遞歸的二叉查找樹的插入操作,分三種情況
void BST_Tree::Tree_Insert(BST_Node *x, BST_Node *z)
{
//已經存在
if(z->key == x->key)
{
cout<<"error:exist"<<endl;
return;
}
//插入到x的左子樹中
else if(z->key < x->key)
{
//x沒有左子樹
if(x->left == NULL)
{
//修改指針,插入操作
x->left = z;
z->p = x;
return;
}
//x有左子樹
else
//對x的左子樹執行插入操作
Tree_Insert(x->left, z);
}
//插入到x的右子樹中,與上面類似
else if(z->key > x->key)
{
if(x->right == NULL)
{
x->right = z;
z->p = x;
}
else
Tree_Insert(x->right, z);
}
}
~~~
12.3-3
最壞是n^2
最好是nlgn
12.3-4
求y的前驅z分為兩種情況,以下分別討論:
(1)y有左孩子,則z是left[y]中最右邊的結點,z沒有右孩子,因此刪除z時直接刪除修改指針即可,沒有問題
(2)y沒有左孩子,則z是y的祖先,y是z右子樹是最左邊的點,又分為兩種情況:
(2.1)若z沒有左孩子,則直接刪除z并修改指針,沒有問題。
(2.2)若z有左孩子,則不直接刪除z,而是用z代替y存在并刪除y。這里會有問題,另一個數據結構中的保存了指向y的指針,但是y的內容轉移到另一個結點上了,指向y的指針指向了一個被釋放的空間。
解決方法:使TREE-DELETE返回刪除后的y的指針,這個值可能會變,可能不變。讓另一個數據結構的y指針指向TREE-DELETE的返回值。
12.3-5
不或交換,反例如圖


12.3-6
當待刪除結點有兩個子樹時,不刪除待刪除結點,而是刪除它的前驅或后繼,用隨機數rand()%2來確定刪除的前驅還是后繼
代碼見文:二
# 四、思考題
### 12-1 具有相同關鍵字元素的二叉樹
見[算法導論-12-1-具有相同關鍵字元素的二叉查找樹](http://blog.csdn.net/mishifangxiangdefeng/article/details/7719138)
### 12-2 基數樹
見[算法導論-12-2-基數樹](http://blog.csdn.net/mishifangxiangdefeng/article/details/7719324)
12-3 隨機構造的二叉查找樹中的平均結點深度
f)待解決
- 前言
- 第6章 堆排序
- 6-3 Young氏矩陣
- 第7章 快速排序
- 第8章 線性時間排序
- 第9章 排序和順序統計學算法導論
- 算法導論 9.1-1 求第二小元素
- 第10章 10.1 棧和隊列
- 第10章 10.2 鏈表
- 第10章 10.3 指針和對象實現
- 第10章 10.4 有根樹的表示
- 第11章-散列表
- 第12章 二叉查找樹
- 第13章 紅黑樹
- 第14章 14.1 動態順序統計
- 算法導論-14-1-最大重疊點
- 算法導論-14-2-Josephus排列
- 第14章 14.3 區間樹
- 第15章 動態規劃
- 第16章 貪心算法
- 第18章 B樹
- 第19章-二項堆
- 第20章 斐波那契堆
- 第21章 用于不相交集合的數據結構
- 第22章 圖的基本算法 22.1 圖的表示
- 第22章 圖算法 22.2 廣度優先搜索
- 第22章 圖算法 22.3 深度優先搜索
- 第22章 圖的基本算法 22.4 拓撲排序
- 第22章 圖的基本算法 22.5 強聯通分支