先贊后看，養(yǎng)成習(xí)慣！！！^ _ ^<3 ?? ?? ??
碼字不易，大家的支持就是我堅(jiān)持下去的動力。點(diǎn)贊后不要忘了關(guān)注我哦！
所屬專欄:C++進(jìn)階

一、二叉搜索樹的概念結(jié)構(gòu)和時(shí)間復(fù)雜度

二叉搜索樹（Binary Search Tree）又稱二叉排序樹（Binary Sort Tree），是一種特殊類型的二叉樹，它所有的根節(jié)點(diǎn)大于左子樹的節(jié)點(diǎn)，小于右子樹的節(jié)點(diǎn)，對二叉搜索樹進(jìn)行中序遍歷，即可得到有序的數(shù)列。二叉搜索樹的時(shí)間復(fù)雜度由樹的高度決定，其搜索、插入和刪除的時(shí)間復(fù)雜度均為 O(log n)，其中 n 是節(jié)點(diǎn)數(shù)。在最壞的情況下，仍然會有 O(n)的時(shí)間復(fù)雜度。

二、二叉搜索樹的插入

首先定義一個(gè)命名空間作用域，在域中進(jìn)行插入操作，構(gòu)造一個(gè)二叉樹的節(jié)點(diǎn)，對節(jié)點(diǎn)進(jìn)行初始化構(gòu)造

namespace key
{template<class K>struct BSTreeNode{typedef BSTreeNode<K> Node;BSTreeNode(const K& key):left(nullptr), right(nullptr),_key(key){}Node* left;Node* right;K _key;};template<class K>class BSTree{public:bool Insert(const K& key){Node* root = new Node(key);if (_root == nullptr){_root = root;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > root->_key){parent = cur;cur = cur->left;}else if (cur->_key < root->_key){parent = cur;cur = cur->right;}else{return false;}}if (parent->_key < root->_key)parent->right = root;elseparent->left = root;return true;}
}

代碼圖解：

三、二叉搜索樹的查找

查找非常簡單按照流程找就行了

typedef BSTreeNode<K> Node;
bool Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->right;}else if (cur->_key > key){cur = cur->left;}else{return true;}}return false;
}

四、二叉搜索樹的刪除（最麻煩，情況最多，一一分析）

3.1首先我們按照一般情況下寫，不考慮特殊情況下

bool Erase(const K& key)
{assert(_root);Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->left;}else if (cur->_key < key){parent = cur;cur = cur->right;}else{if (cur->left == nullptr){if (parent->left == cur){parent->left = cur->right;}else{parent->right = cur->right;}delete cur;return true;}else if (cur->right == nullptr){if (parent->left == cur){parent->left = cur->left;}else{parent->right = cur->left;}delete cur;return true;}else{Node* pminleft = cur;Node* minleft = cur->right;while (minleft->left){pminleft = minleft;minleft = minleft->left;}cur->_key = minleft -> _key;if (minleft == pminleft->left)pminleft->left = minleft->right;elsepminleft->right = minleft->right;delete minleft;return true;}}}return false;
}

代碼圖解（解釋找到時(shí)候的情況）

4.1.1左為空的情況（與右為空的情況差不多）

4.1.2兩邊都不為空的情況下

4.1其次我們考慮極端情況，如果剛好是整體樹的根要刪除

調(diào)整代碼如下

				if (cur->left == nullptr){if (cur == _root){_root = cur->right;}else{if (parent->left == cur){parent->left = cur->right;}else{parent->right = cur->right;}}delete cur;return true;}else if (cur->right == nullptr){if (cur == _root){_root = cur->left;}else{if (parent->left == cur){parent->left = cur->left;}else{parent->right = cur->left;}}delete cur;return true;
}

五、二叉搜索樹的中序遍歷

這里我們用了一個(gè)小技巧，就是通過類里面的函數(shù)調(diào)用類里面的私有成員

//中序遍歷
void _Inorder()
{Inorder(_root);
}
private://中序遍歷void Inorder(Node* root){if (root == nullptr)return;Inorder(root->left);cout << root->_key << ' ';Inorder(root->right);}Node* _root = nullptr;

六、二叉搜索樹的拷貝構(gòu)造函數(shù)，析構(gòu)函數(shù)，賦值操作

6.1 賦值操作（比較簡單）

BSTree<K>& operator=(const BSTree& root)
{swap(_root, root->_root);return *this;
}

6.2拷貝構(gòu)造

BSTree(const BSTree<K>& t)
{_root = Copy(t._root);
}
Node* Copy(Node* root)
{if (root == nullptr)return nullptr;Node* newroot = new Node(root->_key);newroot->left = Copy(root->left);newroot->right = Copy(root->right);return newroot;
}

6.3析構(gòu)函數(shù)

~BSTree()
{Distroy(_root);
}
void Distroy(Node* root)
{if (root == nullptr)return;Distroy(root->left);Distroy(root->right);delete root;
}

七、全部源碼展現(xiàn)（遞歸玩法的代碼也傳進(jìn)來了，下次講解）

#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;namespace key
{template<class K>struct BSTreeNode{typedef BSTreeNode<K> Node;BSTreeNode(const K& key):left(nullptr), right(nullptr),_key(key){}Node* left;Node* right;K _key;};template<class K>class BSTree{public://查BSTree() = default;//自動生成默認(rèn)構(gòu)造~BSTree(){Distroy(_root);}BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(const BSTree& root){swap(_root, root->_root);return *this;}typedef BSTreeNode<K> Node;bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->right;}else if (cur->_key > key){cur = cur->left;}else{return true;}}return false;}//增bool Insert(const K& key){Node* root = new Node(key);if (_root == nullptr){_root = root;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > root->_key){parent = cur;cur = cur->left;}else if (cur->_key < root->_key){parent = cur;cur = cur->right;}else{return false;}}if (parent->_key < root->_key)parent->right = root;elseparent->left = root;return true;}//刪bool Erase(const K& key){assert(_root);Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->left;}else if (cur->_key < key){parent = cur;cur = cur->right;}else{if (cur->left == nullptr){if (cur == _root){_root = cur->right;}else{if (parent->left == cur){parent->left = cur->right;}else{parent->right = cur->right;}}delete cur;return true;}else if (cur->right == nullptr){if (cur == _root){_root = cur->left;}else{if (parent->left == cur){parent->left = cur->left;}else{parent->right = cur->left;}}delete cur;return true;}else{Node* pminleft = cur;Node* minleft = cur->right;while (minleft->left){pminleft = minleft;minleft = minleft->left;}cur->_key = minleft -> _key;if (minleft == pminleft->left)pminleft->left = minleft->right;elsepminleft->right = minleft->right;delete minleft;return true;}}}return false;}/		//遞歸玩法//增bool _InsertR(const K& key){_Insert(_root,key);}bool _EraseR(const K& key){_Erase(_root, key);}bool _FindR(const K& key){_Find(_root,key);}void Distroy(Node* root){if (root == nullptr)return;Distroy(root->left);Distroy(root->right);delete root;}//中序遍歷void _Inorder(){Inorder(_root);}private://中序遍歷void Inorder(Node* root){if (root == nullptr)return;Inorder(root->left);cout << root->_key << ' ';Inorder(root->right);}bool _Insert(Node*& root,const K& key){if (root == nullptr){Node* newroot = new Node(key);root = newroot;return true;}if (root->_key > key){_Insert(root->left, key);}else if (root->_key < key){_Insert(root->right, key);}elsereturn false;}Node& _Find(Node*& root, const K& key){if (root == nullptr)return nullptr;if (root->_key > key){_Find(root->left);}else if (root->_key < key){_Find(root->right);}else{return root;}}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newroot = new Node(root->_key);newroot->left = Copy(root->left);newroot->right = Copy(root->right);return newroot;}bool _Erase(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key > key){return _Erase(root->left,key);}else if(root->_key < key){return _Erase(root->right ,key);}else{Node* minright = root->right;while (minright->left)minright = minright->left;swap(root->_key,minright->_key);minright->right = minright->right;delete minright;return true;}}Node* _root = nullptr;};
}