目錄
- 一、概念、性質
- 二、二叉搜索樹的實現
- 1. 結構
- 2. 查找
- 3. 插入
- 4. 刪除
- 5. 中序遍歷
- 中序前驅/后繼結點
一、概念、性質
二叉搜索樹(Binary Search Tree),簡寫BST,又稱為二叉查找樹
它滿足:
- 空樹是一顆二叉搜索樹
- 對于任意結點 node ,它的左右孩子如果不為空 ,滿足:
-
- 左子樹上所有結點的值都小于node的值
-
- 右子樹上所有結點的值都大于node的值
- 不存在數值重復的結點
如下圖,圖(1)是二叉搜索樹,圖(2)、圖(3)不是二叉搜索樹
圖(2)中不滿足 70 < 50
圖(3)中不滿足 30 < 10
之所以叫做二叉搜索樹,是因為在BST中搜索一個值是很簡單的
例如圖(1)中要查找40
從根結點出發,40比50小,來到根結點的左孩子30,40比30大,來到30的右孩子40,40等于40,這樣就找到了
例如圖(1)中要查找10
從根結點出發,10比50小,來到根節點的左孩子30,10比30小,來到30的左孩子20,10比20小,來到20的左孩子null,所以沒有10這個結點
對圖(1)進行中序遍歷,得到 20 30 40 50 60
發現是一個有序的序列
所以對二叉搜索樹進行中序遍歷,會得到一個有序的序列
二、二叉搜索樹的實現
1. 結構
定義一個二叉搜索樹很簡單,就和定義一個二叉樹的結構一樣,需要包含 數據、左右孩子指針
// 定義結點結構
type TSNode struct {data intleft *TSNoderight *TSNode
}
2. 查找
查找一個值target,從根結點開始,遞歸進行比較。
如果等于根結點,找到返回
如果小于根結點則走到左子樹,在左子樹中找
如果大于根結點則走到右子樹,在右子樹中找
// 判斷結點是否存在
func (t *TSNode) Search(data int) *TSNode {if t == nil {return nil}if t.data == data { //找到了 返回結點return t}if data < t.data { //要找的數據小于根結點 向左找return t.left.Search(data)} else { //要找的數據大于根結點 向右找return t.right.Search(data)}
}
3. 插入
向二叉搜索樹插入數據data ,分為兩種情況
- 樹為空,定義一個新結點儲存data,直接 根結點 = 新結點
- 樹不為空,和結點進行比較(和查找數據步驟一樣),直到結點為空,將新結點插入
如向圖(1)中插入數據35
- 首先和根結點50進行比較,小于50,走到左孩子30
- 和30進行比較,大于30,走到30的右孩子40
- 和40進行比較,小于40,走到40的左孩子 null,將35 插入40 左孩子
最終得到
// 插入數據
func (t *TSNode) Insert(data int) {newNode := &TSNode{data,nil,nil,}//如果根結點為空 直接插入if t == nil {t = newNodereturn}//根結點不為空 判斷if data < t.data { //小于根結點數據 向左找if t.left == nil { //左孩子為空 直接賦值t.left = newNode} else {t.left.Insert(data) //左孩子不為空 遍歷左孩子 找}} else {if t.right == nil {t.right = newNode} else {t.right.Insert(data)}}
}
4. 刪除
刪除二叉搜索樹的數據分為三種情況
- 要刪除的結點沒有左右孩子
- 要刪除的結點沒有左孩子或右孩子
- 要刪除的結點既有左孩子也有右孩子
有這樣一顆二叉搜索樹,下面第一二種拿這個舉例子
- 刪除的結點沒有左右孩子
直接刪除結點就可以
例如刪除上圖中的25,直接刪除25得到
- 要刪除的結點只有左孩子或只有右孩子
如果只有右孩子,比如刪除圖中的60
直接讓60父結點與60的右孩子連接,將60刪除就可以
得到:
3. 要刪除的結點既有左孩子也有右孩子
這里要引入中序后繼和中序前驅的概念,我把這兩個概念放在最后了
比如要刪除30,找到30的中序后繼結點或者中序前驅結點,哪個都可以,就拿中序后繼結點舉例子
30的中序后繼結點是35,將35的值賦給30這個節點,再對30的右子樹進行刪除中序后繼結點的操作就可以了
使用中序前驅結點一樣,將中序前驅節點的值賦給要刪除的節點的值,再對要刪除的節點的左子樹進行刪除中序前驅節點的操作
實現刪除操作的代碼:
首先要找到要刪除的結點, if、else if、else 就是在找要刪除的結點
// 刪除結點
func (t *TSNode) Delete(data int) *TSNode {//查找結點 -- 查找到要找的結點,分情況對結點進行刪除操作if t == nil {return nil}if data < t.data { //要刪除的數據小于根結點//遞歸查找左子樹t.left = t.left.Delete(data)} else if data > t.data {//遞歸查找右子樹t.right = t.right.Delete(data)} else { //查找到了要刪除的數據//此時t是要刪除的結點 分情況if t.left == nil && t.right == nil { //如果左右孩子都是空 直接刪除 返回空return nil}//只有一個結點if t.left == nil { //只有一個右結點 父結點和左孩子結點相連return t.right}if t.right == nil { //只有一個左結點 父結點和右孩子結點相連return t.left}//左右孩子結點都存在//找到 中序后繼結點 -- 右孩子一直向左找minNode := t.right.MinNode()//用這個結點替換要刪除的結點t.data = minNode.data//刪除中序后繼結點--因為是查找的右孩子的中序后繼,所以調整右子樹t.right = t.right.Delete(minNode.data)}return t
}// 查找中序后繼結點
func (t *TSNode) MinNode() *TSNode {if t.left == nil {return t}return t.left.MinNode()
}
5. 中序遍歷
使用遞歸遍歷,和二叉樹的中序遍歷一樣
先遞歸左子樹,再打印節點的值,最后遞歸右子樹
// 中序遍歷
func (t *TSNode) InOrder() {if t == nil {return}t.left.InOrder()fmt.Printf("%d ", t.data)t.right.InOrder()
}
中序前驅/后繼結點
-
中序后繼結點:在中序遍歷中緊跟在某個節點后面的節點
怎么找中序后繼結點呢?
先走到一個結點Node 的右孩子,再從右孩子不斷向左走,直到某個節點的左孩子為空,那這個結點就是Node 的中序后繼結點
比如要找30的中序后繼結點,30走到40,40向左走到35,35的左孩子為空,那35就是30的后繼結點 -
中序前驅結點:在中序遍歷中在某個結點前一個的結點
怎么找中序前驅結點呢?
先走到一個結點Node 的左孩子,再從左孩子不斷向右走,直到某個節點的右孩子為空,那這個結點就是Node 的中序前驅結點
比如要找30的中序前驅結點,30走到左孩子20,20向右走到25,25的右孩子為空,所以25就是30的中序前驅結點