二叉搜索樹(shù)

1. 二叉搜索樹(shù)的概念和介紹

??二叉搜索樹(shù)又稱(chēng)二叉排序樹(shù)，它或者是一棵空樹(shù)，或者是具有以下性質(zhì)的二叉樹(shù):

??（1）若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值

??（2）若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值

??（3）它的左右子樹(shù)也分別為二叉搜索樹(shù)

??二叉搜索樹(shù)（Binary Search Tree）的每個(gè)節(jié)點(diǎn)包含三個(gè)屬性：鍵（key）、左孩子（lchild）和右孩子（rchild）。 鍵用于存儲(chǔ)節(jié)點(diǎn)的值，左孩子和右孩子分別指向左子樹(shù)和右子樹(shù)的根節(jié)點(diǎn)。

??二叉搜索樹(shù)的結(jié)構(gòu)類(lèi)似于一個(gè)倒置的樹(shù)，最底層的節(jié)點(diǎn)位于樹(shù)的頂部，每個(gè)節(jié)點(diǎn)都有一個(gè)鍵值，并且每個(gè)節(jié)點(diǎn)的左子樹(shù)上的所有節(jié)點(diǎn)的鍵值都小于該節(jié)點(diǎn)的鍵值，而右子樹(shù)上的所有節(jié)點(diǎn)的鍵值都大于該節(jié)點(diǎn)的鍵值。這種結(jié)構(gòu)使得二叉搜索樹(shù)在處理有序數(shù)據(jù)時(shí)非常高效。

??基于以上性質(zhì)，二叉搜索樹(shù)在查找、插入和刪除操作上具有較好的效率，時(shí)間復(fù)雜度為O(logn)。

??基于二叉搜索樹(shù)的特殊結(jié)構(gòu)，二叉搜索樹(shù)的中序遍歷（Inorder Traversal）按照左子樹(shù)、根節(jié)點(diǎn)、右子樹(shù)的順序遍歷二叉樹(shù)，它會(huì)按照從大到小的順序輸出二叉樹(shù)中的所有元素。

??以下這顆二叉搜索樹(shù)的中序遍歷結(jié)果：1 3 4 6 7 8 10 13 14

?????????????

2. 二叉搜索樹(shù)的簡(jiǎn)單實(shí)現(xiàn)

??和之前的二叉樹(shù)實(shí)現(xiàn)類(lèi)似，二叉搜索樹(shù)的實(shí)現(xiàn)只需要在二叉樹(shù)的實(shí)現(xiàn)基礎(chǔ)上，將左右元素根據(jù)和根節(jié)點(diǎn)的大小，重新考慮排列順序即可。

??定義二叉搜索樹(shù)的節(jié)點(diǎn)：

//搜索二叉樹(shù)創(chuàng)建節(jié)點(diǎn)
template<class K>
struct BSTreeNode
{//左右節(jié)點(diǎn)和節(jié)點(diǎn)值keyBSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;//二叉樹(shù)節(jié)點(diǎn)構(gòu)造函數(shù)BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};

??定義二叉搜索樹(shù)類(lèi)：

//創(chuàng)建二叉搜索樹(shù)
template<class K>
class BSTree
{//便于書(shū)寫(xiě)B(tài)Node節(jié)點(diǎn)typedef BSTreeNode<K> BNode;public://二叉搜索樹(shù)構(gòu)造函數(shù)BSTree():_root(nullptr){}private:BNode* _root;
};

?????????????

2.1二叉搜索樹(shù)的插入

??二叉搜索樹(shù)的插入過(guò)程可以分為以下步驟：

??（1）如果二叉搜索樹(shù)為空，創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將待插入關(guān)鍵字放入新節(jié)點(diǎn)的數(shù)據(jù)域。將新節(jié)點(diǎn)作為根節(jié)點(diǎn)，左右子樹(shù)均為空。

??（2）如果二叉搜索樹(shù)非空，將待查找關(guān)鍵字與根節(jié)點(diǎn)關(guān)鍵字進(jìn)行比較。如果小于根節(jié)點(diǎn)關(guān)鍵字，則將待查找關(guān)鍵字插入左子樹(shù)中；如果大于根節(jié)點(diǎn)關(guān)鍵字，則將待查找關(guān)鍵字插入右子樹(shù)中。

??重復(fù)上述步驟，直到找到合適的位置插入待插入的關(guān)鍵字。

??在插入過(guò)程中，需要保持二叉搜索樹(shù)的性質(zhì)：任意節(jié)點(diǎn)的左子樹(shù)的所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值，右子樹(shù)的所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值。如果插入后破壞了這種性質(zhì)，需要進(jìn)行調(diào)整。

?
??非遞歸的實(shí)現(xiàn)：

//二叉樹(shù)插入節(jié)點(diǎn)
bool BSInsert(const K& key)
{//如果該樹(shù)為空樹(shù)，直接創(chuàng)建節(jié)點(diǎn)if (_root == nullptr){_root = new BNode(key);return true;}//找到二叉樹(shù)所在的節(jié)點(diǎn)BNode* parent = nullptr;BNode* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}//插入節(jié)點(diǎn)cur = new BNode(key);if (parent->_key > key){parent->_left = cur;}else {parent->_right = cur;}return true;
}

?
??遞歸的實(shí)現(xiàn)：

bool _BSInsertR(BNode*& root, const K& key)//這里傳&,直接可以得到地址
{if (root == nullptr){root = new BNode(key);return true;}if (root->_key < key){_BSInsertR(root->_right, key);}else if (root->_key > key){_BSInsertR(root->_left, key);}else{return false;}
}

?????????????

2.2二叉搜索樹(shù)的查找

??二叉搜索樹(shù)的查找實(shí)現(xiàn)過(guò)程可以分為以下步驟：

??（1）將待查找關(guān)鍵字與根節(jié)點(diǎn)關(guān)鍵字進(jìn)行比較。如果相等，則找到了目標(biāo)關(guān)鍵字，查找結(jié)束。

??（2）如果待查找關(guān)鍵字小于根節(jié)點(diǎn)關(guān)鍵字，則將待查找關(guān)鍵字放入左子樹(shù)中繼續(xù)查找。

??（3）如果待查找關(guān)鍵字大于根節(jié)點(diǎn)關(guān)鍵字，則將待查找關(guān)鍵字放入右子樹(shù)中繼續(xù)查找。

??重復(fù)上述步驟，直到找到目標(biāo)關(guān)鍵字，或者搜索到了空節(jié)點(diǎn)（表示未找到目標(biāo)關(guān)鍵字）。

??在查找過(guò)程中，由于二叉搜索樹(shù)是基于二分的思想，所以每次比較都可以排除一半的搜索空間，因此時(shí)間復(fù)雜度為O(logn)。

?
??非遞歸實(shí)現(xiàn)：

//查找二叉樹(shù)的節(jié)點(diǎn)
bool BSFind(const K& key)
{BNode* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}return false;
}

??遞歸實(shí)現(xiàn)：

bool _BSFindR(BNode* root, const K& key)
{if (root == nullptr){return false;}if (root->_key < key){return _BSFindR(root->_right, key);}else if (root->_key > key){return _BSFindR(root->_left, key);}else{return true;}
}

?????????????

2.3二叉搜索樹(shù)的遍歷

??二叉搜索樹(shù)常使用中序遍歷，而不是前序遍歷和后序遍歷。

??因?yàn)橹行虮闅v的特點(diǎn)是先訪問(wèn)左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)。 在訪問(wèn)左子樹(shù)時(shí)，先訪問(wèn)左子樹(shù)的左子樹(shù)，再訪問(wèn)左子樹(shù)的右子樹(shù)；在訪問(wèn)右子樹(shù)時(shí)，先訪問(wèn)右子樹(shù)的左子樹(shù)，再訪問(wèn)右子樹(shù)的右子樹(shù)。

??二叉搜索樹(shù)中序遍歷的結(jié)果是按照從小到大的順序輸出二叉搜索樹(shù)中的所有元素。

??二叉搜索樹(shù)的中序遍歷過(guò)程可以分為以下步驟：

??（1）首先遍歷左子樹(shù)，訪問(wèn)左子樹(shù)中的所有節(jié)點(diǎn)，并按照中序遍歷的順序遞歸地訪問(wèn)它們的右子樹(shù)。

??（2）然后訪問(wèn)根節(jié)點(diǎn)。

??（3）最后遍歷右子樹(shù)，訪問(wèn)右子樹(shù)中的所有節(jié)點(diǎn)，并按照中序遍歷的順序遞歸地訪問(wèn)它們的左子樹(shù)。

??遞歸實(shí)現(xiàn)：

void _BSInOrder(BNode* root)
{if (root == nullptr){return;}_BSInOrder(root->_left);printf("%d ", root->_key);_BSInOrder(root->_right);
}

?????????????

2.4二叉搜索樹(shù)的刪除

??二叉搜索樹(shù)的刪除操作可以按照以下步驟實(shí)現(xiàn)：

??（1）首先，找到要?jiǎng)h除的節(jié)點(diǎn)?？梢酝ㄟ^(guò)中序遍歷或者二分查找等方式找到要?jiǎng)h除的節(jié)點(diǎn)。

??（2）如果要?jiǎng)h除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)（沒(méi)有子節(jié)點(diǎn)），直接將該節(jié)點(diǎn)從二叉搜索樹(shù)中刪除即可。

??（3）如果要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，將該節(jié)點(diǎn)的子節(jié)點(diǎn)與其父節(jié)點(diǎn)相連，刪除該節(jié)點(diǎn)即可。

??（4）如果要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，需要找到該節(jié)點(diǎn)的左子樹(shù)中的最大節(jié)點(diǎn)（或者右子樹(shù)中的最小節(jié)點(diǎn)），用該節(jié)點(diǎn)代替要?jiǎng)h除的節(jié)點(diǎn)的位置，然后刪除該最小（或最大）節(jié)點(diǎn)。

??在實(shí)現(xiàn)刪除操作時(shí)，需要注意保持二叉搜索樹(shù)的性質(zhì)，即任意節(jié)點(diǎn)的左子樹(shù)的所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值，右子樹(shù)的所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值。同時(shí)，刪除操作可能會(huì)導(dǎo)致二叉搜索樹(shù)的平衡被破壞，需要進(jìn)行相應(yīng)的調(diào)整操作。

??（1）當(dāng)沒(méi)有葉子結(jié)點(diǎn)，或者只有一個(gè)子節(jié)點(diǎn)的情況：

??（2）當(dāng)左右都有子節(jié)點(diǎn)的情況：

?
??非遞歸實(shí)現(xiàn)：

//刪除二叉樹(shù)中的節(jié)點(diǎn)
bool BSErase(const K& key)
{BNode* cur = _root;BNode* parent = nullptr;//先要找到所刪除的節(jié)點(diǎn)while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else//找到了所要?jiǎng)h除的節(jié)點(diǎn){if (cur->_left == nullptr)//當(dāng)左節(jié)點(diǎn)為空節(jié)點(diǎn){if (cur == _root)//cur為根節(jié)點(diǎn){_root = cur->_right;}else//cur不為空節(jié)點(diǎn){if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}else if(cur->_right==nullptr)//當(dāng)右節(jié)點(diǎn)為空節(jié)點(diǎn){if (cur == _root)//cur為空節(jié)點(diǎn){_root = cur->_left;}else//cur不為空節(jié)點(diǎn){if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}else//當(dāng)左右節(jié)點(diǎn)都不為空節(jié)點(diǎn){//找代替節(jié)點(diǎn)BNode* parent = cur;BNode* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur=leftMax;}delete cur;return true;}}return false;
}

??遞歸實(shí)現(xiàn)：

bool _BSEraseR(BNode* &root, const K& key)
{if (root == nullptr){return false;}if (root->_key < key){_BSEraseR(root->_right, key);}else if (root->_key > key){_BSEraseR(root->_left, key);}else{BNode* del = root;//1.左為空//2.右為空//3.左右都不為空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{BNode* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _BSEraseR(root->_left, key);}delete del;return true;}
}

?????????????

2.5完整代碼和測(cè)試

??完整代碼：

#pragma once//搜索二叉樹(shù)創(chuàng)建節(jié)點(diǎn)
template<class K>
struct BSTreeNode
{//左右節(jié)點(diǎn)和節(jié)點(diǎn)值keyBSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;//二叉樹(shù)節(jié)點(diǎn)構(gòu)造函數(shù)BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};//創(chuàng)建搜索二叉樹(shù)
template<class K>
class BSTree
{//便于書(shū)寫(xiě)B(tài)Node節(jié)點(diǎn)typedef BSTreeNode<K> BNode;public://搜索二叉樹(shù)構(gòu)造函數(shù)BSTree():_root(nullptr){}//二叉樹(shù)插入節(jié)點(diǎn)bool BSInsert(const K& key){//如果該樹(shù)為空樹(shù)，直接創(chuàng)建節(jié)點(diǎn)if (_root == nullptr){_root = new BNode(key);return true;}//找到二叉樹(shù)所在的節(jié)點(diǎn)BNode* parent = nullptr;BNode* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}//插入節(jié)點(diǎn)cur = new BNode(key);if (parent->_key > key){parent->_left = cur;}else {parent->_right = cur;}return true;}//查找二叉樹(shù)的節(jié)點(diǎn)bool BSFind(const K& key){BNode* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}return false;}//刪除二叉樹(shù)中的節(jié)點(diǎn)bool BSErase(const K& key){BNode* cur = _root;BNode* parent = nullptr;//先要找到所刪除的節(jié)點(diǎn)while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else//找到了所要?jiǎng)h除的節(jié)點(diǎn){if (cur->_left == nullptr)//當(dāng)左節(jié)點(diǎn)為空節(jié)點(diǎn){if (cur == _root)//cur為根節(jié)點(diǎn){_root = cur->_right;}else//cur不為空節(jié)點(diǎn){if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}else if(cur->_right==nullptr)//當(dāng)右節(jié)點(diǎn)為空節(jié)點(diǎn){if (cur == _root)//cur為空節(jié)點(diǎn){_root = cur->_left;}else//cur不為空節(jié)點(diǎn){if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}else//當(dāng)左右節(jié)點(diǎn)都不為空節(jié)點(diǎn){//找代替節(jié)點(diǎn)BNode* parent = cur;BNode* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur=leftMax;}delete cur;return true;}}return false;}//二叉樹(shù)的中序遍歷void BSInOrder(){_BSInOrder(_root);cout << endl;}//遞歸實(shí)現(xiàn)二叉樹(shù)的查找bool BSFindR(const K& key){return _BSFindR(_root, key);}//遞歸實(shí)現(xiàn)二叉樹(shù)的插入節(jié)點(diǎn)bool BSInsertR(const K& key){return _BSInsertR(_root, key);}//遞歸實(shí)現(xiàn)二叉樹(shù)的刪除節(jié)點(diǎn)bool BSEraseR(const K& key){return _BSEraseR(_root, key);}private://遞歸二叉樹(shù)刪除的封裝實(shí)現(xiàn)bool _BSEraseR(BNode* &root, const K& key){if (root == nullptr){return false;}if (root->_key < key){_BSEraseR(root->_right, key);}else if (root->_key > key){_BSEraseR(root->_left, key);}else{BNode* del = root;//1.左為空//2.右為空//3.左右都不為空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{BNode* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _BSEraseR(root->_left, key);}delete del;return true;}}//遞歸二叉樹(shù)插入的封裝實(shí)現(xiàn)bool _BSInsertR(BNode*& root, const K& key)//這里傳&,直接可以得到地址{if (root == nullptr){root = new BNode(key);return true;}if (root->_key < key){_BSInsertR(root->_right, key);}else if (root->_key > key){_BSInsertR(root->_left, key);}else{return false;}}//遞歸二叉樹(shù)查找的封裝實(shí)現(xiàn)bool _BSFindR(BNode* root, const K& key){if (root == nullptr){return false;}if (root->_key < key){return _BSFindR(root->_right, key);}else if (root->_key > key){return _BSFindR(root->_left, key);}else{return true;}}//為了遞歸實(shí)現(xiàn)，進(jìn)行一層封裝void _BSInOrder(BNode* root){if (root == nullptr){return;}_BSInOrder(root->_left);printf("%d ", root->_key);_BSInOrder(root->_right);}private:BNode* _root;
};

?
??簡(jiǎn)單測(cè)試：

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
using namespace std;#include"BinarySearchTree.h"void BSTree_test1()
{BSTree<int> t;t.BSInsert(5);t.BSInsert(8);t.BSInsert(6);t.BSInsert(1);t.BSInsert(3);t.BSInsert(2);t.BSInsert(4);t.BSInOrder();cout << "是否存在二叉樹(shù)的值為1:";if (t.BSFind(1))cout << "存在";else cout << "不存在";cout << endl;int arr[] = { 5,3,1,2,4,9,8,6,7,10 };BSTree<int> t1;for (auto e : arr){t1.BSInsert(e);}t1.BSInOrder();t1.BSErase(3);t1.BSInOrder();cout << "是否存在二叉樹(shù)的值為1:";if (t1.BSFindR(1))cout << "存在";else cout << "不存在";cout << endl;t1.BSInsertR(11);t1.BSInOrder();t1.BSEraseR(11);t1.BSInOrder();}int main()
{BSTree_test1();return 0;
}

這里就是數(shù)據(jù)結(jié)構(gòu)中二叉搜索樹(shù)的基本介紹了😉
如有錯(cuò)誤?望指正，最后祝大家學(xué)習(xí)進(jìn)步?天天開(kāi)心?🎉

?????????????