資料結構高階--二元搜尋樹（原理+實現）
2022-12-01 12:00:38
二元搜尋樹
概念
二元搜尋樹又稱為二叉排序樹，因為這棵樹的中序遍歷是有序的。二元搜尋樹總結起來有以下幾個性質：
- 若它的左子樹不為空，則左子樹上所有節點的值都小於根節點的值
- 若它的右子樹不為空，則右子樹上所有節點的值都大於於根節點的值
- 它的左右子樹都是二元搜尋樹
- 這棵樹中沒有重複的元素
舉個例子：
二元搜尋樹的實現
基本框架
template <class K,class V>
struct BST_Node
{
BST_Node<K,V>* left;
BST_Node<K,V>* right;
K key;
V value;
//建構函式
BST_Node(const K& key, const V& value):left(nullptr),right(nullptr),key(key),value(value)
{}
};
template <class K,class V>
class BST_Tree
{
typedef BST_Node<K,V> Node;
public:
private:
Node* root = nullptr;
};
要實現的介面
bool Insert(const K& key,const V& value);//二元搜尋樹的插入
void InOrder();//列印功能，採用中序遍歷（遞迴）
Node* Find(const K& key);//二元搜尋樹的查詢
bool Erase(const K& key);//二元搜尋樹的刪除
二元搜尋樹的插入
插入分為下面幾個步驟：
- 先判斷樹是否為空，為空就讓要插入的這個節點作為根節點，然後結束
- 確定要插入節點的位置
- 用一個cur記錄當前節點，parent記錄父節點
- 要插入節點的值如果比當前節點的值小，cur就往左走，如果比當前節點的值大，就往右子樹走，如果等於就返回false，表面這棵樹中有這個資料，不需要插入
//二元搜尋樹的插入
bool Insert(const K& key,const V& value)
{
//沒有節點的時候就是根節點
if (root == nullptr)
{
root = new Node(key,value);
return true;
}
//用一個父節點記錄cur的上一個節點
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
parent = cur;
//小於往左走
if (key < cur->key)
{
cur = cur->left;
}
else if (key > cur->key)
{
cur = cur->right;
}
else
return false;
}
cur = new Node(key,value);
//判斷應該插在父節點的左邊還是右邊
if (cur->key < parent->key)
{
parent->left = cur;
}
else
{
parent->right = cur;
}
return true;
}
列印二元搜尋樹（中序遍歷）
//中序遍歷（遞迴）
void InOrder()
{
_InOrder(root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
else
{
_InOrder(root->left);
cout << root->key << ":" << root->value << endl;
_InOrder(root->right);
}
}
二元搜尋樹的查詢
查詢的步驟如下：（和插入的步驟有些類似）
- 如果查詢值key比當前節點的值小，就往左子樹走
- 如果查詢值key比當前節點的值大，就往右子樹走
- 如果查詢值key和當前節點的值相等，就返回當前節點的指標
//二元搜尋樹的查詢
Node* Find(const K& key)
{
if (root == nullptr)
{
return nullptr;
}
Node* cur = root;//遍歷結點
while (cur)
{
//小於往左走
if (cur->key > key)
{
cur = cur->left;
}
else if (cur->key < key)
{
cur = cur->right;
}
else
{
return cur;
}
}
return nullptr;
}
二元搜尋樹的刪除（難）
分四種情況：我們一個一個來討論
以下面這顆樹為例：
情景一：
情景二：
還要分析一種特殊的情況，就是此時2沒有父親節點，也就是自己為根時，看下面如何操作
情景三：
該節點如果為根節點，就讓自己的右孩子變成根節點
情景四：
總結： 一共有四種情況，但是情況1可以歸為情況3，因為它也是左為空，所以整體處理下來是三種情況
//二元搜尋樹的刪除
bool Erase(const K& key)
{
//樹為空，刪除失敗
if (root == nullptr)
{
return false;
}
//parent始終是cur的父親節點
//cur就是要找的刪除的當前節點
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
//小於往左邊走
if (key < cur->key)
{
parent = cur;
cur = cur->left;
}
else if (key > cur->key)
{
parent = cur;
cur = cur->right;
}
else
{
// 找到了，開始刪除
// 1.左右子樹都為空，直接刪除，可以歸類為左為空
// 2.左右子樹只有一邊為空，左為空，父親指向我的右，右為空，父親指向我的左
// 3.左右子樹都不為空，取左子樹最大的節點或右子樹最小的節點和要刪除的節點交換，然後再刪除
//當前情況是情景三，刪除的節點它的左為空，右未知
if (cur->left == nullptr)
{
// 要刪除節點為根節點時，直接把右子樹的根節點賦值給——root
// 根節點的話會導致parent為nullptr
if (root == cur)
{
root = root->right;
}
else
{
//左為空，父親指向我的右
//判斷cur在父親的左還是右
if (parent->left == cur)
{
parent->left = cur->right;
}
else
{
parent->right = cur->right;
}
}
delete cur;
cur = nullptr;
}
//當前情況是情景二，刪除節點它的右為空，左未知
else if (cur->right == nullptr)
{
if (root ==cur )
{
root = root->left;
}
else
{
//右為空，父親指向我的左
//判斷cur在父親的左還是右
if (parent->left == cur)
{
parent->left = cur->left;
}
else
{
parent->right = cur->left;
}
}
delete cur;
cur = nullptr;
}
//只剩下情景四
else
{
//找右子樹中最小的節點，當前cur就是要刪除的節點
Node* rightMinParent = cur;
Node* rightMin = cur->right;//去右子樹找最小的節點
while (rightMin->left)
{
rightMinParent = rightMin;
rightMin = rightMin->left;
}
//替代刪除
cur->key = rightMin->key;
//轉化成了情景三，左孩子為空
if (rightMinParent->left == rightMin)
rightMinParent->left = rightMin->right;
else
rightMinParent->right = rightMin->right;
delete rightMin;
rightMin = nullptr;
}
return true;
}
}
return false;
}
完整程式碼以及測試
#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入標頭檔案
#include<string>//C++中的字串
using namespace std; //標準名稱空間
template <class K >
struct BST_Node
{
BST_Node<K>* left;
BST_Node<K>* right;
K key;
//建構函式
BST_Node(const K& key):left(nullptr),right(nullptr),key(key)
{}
};
template <class K>
class BST_Tree
{
typedef BST_Node<K> Node;
public:
//二元搜尋樹的插入
bool Insert(const K& key)
{
//沒有節點的時候就是根節點
if (root == nullptr)
{
root = new Node(key);
return true;
}
//用一個父節點記錄cur的上一個節點
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
parent = cur;
//小於往左走
if (key < cur->key)
{
cur = cur->left;
}
else if (key > cur->key)
{
cur = cur->right;
}
else
return false;
}
cur = new Node(key);
//判斷應該插在父節點的左邊還是右邊
if (cur->key < parent->key)
{
parent->left = cur;
}
else
{
parent->right = cur;
}
return true;
}
//中序遍歷（遞迴）
void InOrder()
{
_InOrder(root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
else
{
_InOrder(root->left);
cout << root->key <<" ";
_InOrder(root->right);
}
}
//二元搜尋樹的查詢
Node* Find(const K& key)
{
if (root == nullptr)
{
return nullptr;
}
Node* cur = root;//遍歷結點
while (cur)
{
//小於往左走
if (cur->key > key)
{
cur = cur->left;
}
else if (cur->key < key)
{
cur = cur->right;
}
else
{
return cur;
}
}
return nullptr;
}
//二元搜尋樹的刪除
bool Erase(const K& key)
{
//樹為空，刪除失敗
if (root == nullptr)
{
return false;
}
//parent始終是cur的父親節點
//cur就是要找的刪除的當前節點
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
//小於往左邊走
if (key < cur->key)
{
parent = cur;
cur = cur->left;
}
else if (key > cur->key)
{
parent = cur;
cur = cur->right;
}
else
{
// 找到了，開始刪除
// 1.左右子樹都為空，直接刪除，可以歸類為左為空
// 2.左右子樹只有一邊為空，左為空，父親指向我的右，右為空，父親指向我的左
// 3.左右子樹都不為空，取左子樹最大的節點或右子樹最小的節點和要刪除的節點交換，然後再刪除
//當前情況是情景三，刪除的節點它的左為空，右未知
if (cur->left == nullptr)
{
// 要刪除節點為根節點時，直接把右子樹的根節點賦值給——root
// 根節點的話會導致parent為nullptr
if (root == cur)
{
root = root->right;
}
else
{
//左為空，父親指向我的右
//判斷cur在父親的左還是右
if (parent->left == cur)
{
parent->left = cur->right;
}
else
{
parent->right = cur->right;
}
}
delete cur;
cur = nullptr;
}
//當前情況是情景二，刪除節點它的右為空，左未知
else if (cur->right == nullptr)
{
if (root ==cur )
{
root = root->left;
}
else
{
//右為空，父親指向我的左
//判斷cur在父親的左還是右
if (parent->left == cur)
{
parent->left = cur->left;
}
else
{
parent->right = cur->left;
}
}
delete cur;
cur = nullptr;
}
//只剩下情景四
else
{
//找右子樹中最小的節點，當前cur就是要刪除的節點
Node* rightMinParent = cur;
Node* rightMin = cur->right;//去右子樹找最小的節點
while (rightMin->left)
{
rightMinParent = rightMin;
rightMin = rightMin->left;
}
//替代刪除
cur->key = rightMin->key;
//轉化成了情景三，左孩子為空
if (rightMinParent->left == rightMin)
rightMinParent->left = rightMin->right;
else
rightMinParent->right = rightMin->right;
delete rightMin;
rightMin = nullptr;
}
return true;
}
}
return false;
}
private:
Node* root = nullptr;
};
void TestBSTree()
{
BST_Tree<int> bt;
int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
for (auto e : arr)
{
cout << "插入 " << e << " 後：";
bt.Insert(e);
bt.InOrder();
}
cout << "------------------------------" << endl;
for (auto e : arr)
{
cout << "刪除 " << e << " 後：";
bt.Erase(e);
bt.InOrder();
}
}
int main()
{
TestBSTree();
system("pause");
return EXIT_SUCCESS;
}
二元搜尋樹的應用
二元搜尋樹有兩種模型：
- K模型： K模型只有key值，節點只儲存key值。這裡主要應用就是查詢判斷某個元素在不在。
- KV模型： KV模型每個key值都對應著一個value，主要應用就是通過key找value。（我們平時查詢單詞就是通過中文找英文，或者通過英文找中文）
上面的測試程式碼是KV模型改成了K模型，接下來我們來看看KV模型的作用
#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入標頭檔案
#include<string>//C++中的字串
using namespace std; //標準名稱空間
template <class K,class V>
struct BST_Node
{
BST_Node<K,V>* left;
BST_Node<K,V>* right;
K key;
V value;
//建構函式
BST_Node(const K& key, const V& value):left(nullptr),right(nullptr),key(key),value(value)
{}
};
template <class K,class V>
class BST_Tree
{
typedef BST_Node<K,V> Node;
public:
//二元搜尋樹的插入
bool Insert(const K& key,const V& value)
{
//沒有節點的時候就是根節點
if (root == nullptr)
{
root = new Node(key,value);
return true;
}
//用一個父節點記錄cur的上一個節點
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
parent = cur;
//小於往左走
if (key < cur->key)
{
cur = cur->left;
}
else if (key > cur->key)
{
cur = cur->right;
}
else
return false;
}
cur = new Node(key,value);
//判斷應該插在父節點的左邊還是右邊
if (cur->key < parent->key)
{
parent->left = cur;
}
else
{
parent->right = cur;
}
return true;
}
//中序遍歷（遞迴）
void InOrder()
{
_InOrder(root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
else
{
_InOrder(root->left);
cout << root->key << ":" << root->value << endl;
_InOrder(root->right);
}
}
//二元搜尋樹的查詢
Node* Find(const K& key)
{
if (root == nullptr)
{
return nullptr;
}
Node* cur = root;//遍歷結點
while (cur)
{
//小於往左走
if (cur->key > key)
{
cur = cur->left;
}
else if (cur->key < key)
{
cur = cur->right;
}
else
{
return cur;
}
}
return nullptr;
}
//二元搜尋樹的刪除
bool Erase(const K& key)
{
//樹為空，刪除失敗
if (root == nullptr)
{
return false;
}
//parent始終是cur的父親節點
//cur就是要找的刪除的當前節點
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
//小於往左邊走
if (key < cur->key)
{
parent = cur;
cur = cur->left;
}
else if (key > cur->key)
{
parent = cur;
cur = cur->right;
}
else
{
// 找到了，開始刪除
// 1.左右子樹都為空，直接刪除，可以歸類為左為空
// 2.左右子樹只有一邊為空，左為空，父親指向我的右，右為空，父親指向我的左
// 3.左右子樹都不為空，取左子樹最大的節點或右子樹最小的節點和要刪除的節點交換，然後再刪除
//當前情況是情景三，刪除的節點它的左為空，右未知
if (cur->left == nullptr)
{
// 要刪除節點為根節點時，直接把右子樹的根節點賦值給——root
// 根節點的話會導致parent為nullptr
if (root == cur)
{
root = root->right;
}
else
{
//左為空，父親指向我的右
//判斷cur在父親的左還是右
if (parent->left == cur)
{
parent->left = cur->right;
}
else
{
parent->right = cur->right;
}
}
delete cur;
cur = nullptr;
}
//當前情況是情景二，刪除節點它的右為空，左未知
else if (cur->right == nullptr)
{
if (root ==cur )
{
root = root->left;
}
else
{
//右為空，父親指向我的左
//判斷cur在父親的左還是右
if (parent->left == cur)
{
parent->left = cur->left;
}
else
{
parent->right = cur->left;
}
}
delete cur;
cur = nullptr;
}
//只剩下情景四
else
{
//找右子樹中最小的節點，當前cur就是要刪除的節點
Node* rightMinParent = cur;
Node* rightMin = cur->right;//去右子樹找最小的節點
while (rightMin->left)
{
rightMinParent = rightMin;
rightMin = rightMin->left;
}
//替代刪除
cur->key = rightMin->key;
//轉化成了情景三，左孩子為空
if (rightMinParent->left == rightMin)
rightMinParent->left = rightMin->right;
else
rightMinParent->right = rightMin->right;
delete rightMin;
rightMin = nullptr;
}
return true;
}
}
return false;
}
private:
Node* root = nullptr;
};
int main()
{
system("pause");
return EXIT_SUCCESS;
}
範例1
英漢字典
void TestBSTree_KV1()
{
// 建立一個簡易的字典
BST_Tree<string, string> dict;
dict.Insert("蘋果", "apple");
dict.Insert("香蕉", "banana");
dict.Insert("橘子", "orange");
dict.Insert("葡萄", "grape");
dict.Insert("apple", "蘋果");
dict.Insert("banana", "香蕉");
dict.Insert("orange", "橘子");
dict.Insert("grape", "葡萄");
string str;
while (cin >> str)
{
BST_Node<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->value << endl;
}
else
{
cout << "本字典無此詞" << endl;
}
}
}
範例2
統計樹
void TestBSTree_KV2()
{
// 統計水果個數
BST_Tree<string, int> countTree;
string strArr[] = { "香蕉","水蜜桃","西瓜","蘋果","香蕉" ,"西瓜","香蕉" ,"蘋果","西瓜","蘋果","蘋果","香蕉" ,"水蜜桃" };
for (auto e : strArr)
{
BST_Node<string, int>* ret = countTree.Find(e);
if (ret == nullptr)
{
// 第一次插入
countTree.Insert(e, 1);
}
else
{
ret->value++;
}
}
countTree.InOrder();
}