欢迎来到我的Blog，点击关注哦?
前言：
在数据结构中学习过二叉树，链式二叉树，顺序二叉树，区别于二者的的一种特殊的二叉树是二叉搜索树
二叉搜索树介绍（BST）
二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树
它具有以下性质：
如果树非空，则左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值，且左右子树各自也是二叉搜索树。二叉搜索树的特点是能够快速执行查找、插入和删除操作，其时间复杂度通常为对数级别.如下，是一个简易的二叉搜索树
二叉搜索树基本操作（BST）
二叉搜索树的存储结构（K模型）
如果构成KV模型仅仅在加一个模板参数就好了二树经典的左右指针，和存储数据声明 template<class K> class BSTTree { public: BSTTree<K>* _left; BSTTree<K>* _right; K _key; BSTTree(const K& key) : _left(nullptr) , _right(nullptr) , _key(key) {} };默认成员函数
拷贝构造
采用递归的方式Node* _Copy(Node* root){ if (root == nullptr) return nullptr; Node* copynode = new Node(root->_key); copynode->_left = _Copy(root->_left); copynode->_right = _Copy(root->_right); return copynode;}赋值运算符号重载
传值拷贝，直接进行交换BST(const BST<K>& copy){ _root = _copy(copy._root);}析构函数
用~BST（）直接实现调用的递归 ~BST(){ _destory(_root);}void _destory(Node* root){ if (root == nullptr) return; _destory(root->_left); _destory(root->_right); delete root; root = nullptr;}BST查找
二叉搜索树的查找操作从根节点开始，根据查找值与当前节点值的关系，选择向左子树或右子树递归查找。如果当前节点的值等于查找值，则找到该节点；如果小于查找值，则向右子树查找；如果大于查找值，则向左子树查找。如果查找过程中到达叶节点仍未找到对应值，则表明该值不存在于树中 迭代
bool Find(const K& key){if (_root == nullptr)return false;Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return true;}}return false;}递归
由于在类的内部，类外参数不能传this指针，采用类内传递的形式，进而实现递归bool Find(const K& key){ return _Find(_root ,key);}bool _Find(Node* root,const K& key){ if (root == nullptr) return false; if (root->_key < key) { return _FindR(root->_right, key); } else if (root->_key > key) { return _FindR(root->_left, key); } else { return true; }}BST插入
插入操作首先检查树是否为空，如果为空，则新建一个包含待插入值的节点作为根节点。如果树不为空，则根据二叉搜索树的性质，从根节点开始向下遍历，直至找到一个空的子节点位置，将新节点插入到该位置。新节点总是作为叶节点插入，以保持树的二叉搜索树属性. 迭代
开始判断树是否为空树建立parent节点记录父亲节点进行遍历，查找叶子节点插入保存父亲的节点作用在进行，叶子节点插入的时候进行判断，新节点和叶子节点的大小关系 bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}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;}}if (key < parent->_key){parent->_left = new Node(key);}else{parent->_right = new Node(key);}return true;}递归
值得注意的点是传参数的时候是指针的引用。好处就是不用进行新节点与父亲节点的判断。bool Insert(const K& key){ return _Insert(_root,key);}bool _Insert(Node*& root ,const K& key){if (root == nullptr){root = new Node(key);return true;}if (key < root->_key){return _Insert(root->_left, key);}else if(key > root->_key ){return _Insert(root->_right, key);}else{return false;}}BST删除
删除操作较为复杂，因为需要考虑被删除节点可能有零个、一个或两个子节点的情况。删除操作通常涉及到找到被删除节点的适当继任者（在有两个子节点的情况下，通常是其右子树中的最小节点或左子树中的最大节点），并用继任者的值替换被删除节点的值，然后删除被替换的节点 迭代
三种情况：
要删除的结点无孩子结点 （叶子节点）要删除的结点只有左孩子结点要删除的结点只有右孩子结点要删除的结点有左、右孩子结点bool Erase(const K& key){ Node* cur = _root; Node* parent = _root; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; }//找到键值 else { //左子树为空 if (cur->_left == nullptr) { //祖先节点为键值 if (cur == _root) { cur = cur->_right; } else { if (parent->_right == cur) { parent->_right = cur->_right; } else { parent->_left = cur->_right; } } }//右子树为空 else if (cur->_right == nullptr) { //祖先节点为键值 if (cur == _root) { _root = cur->_left; } else { if (parent->_right == cur) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } } } else//左右子树均存在，查找右子树最大节点 { Node* leftMax = cur->_left; while (leftMax->_right) { parent = leftMax; leftMax = leftMax->_right; } swap(leftMax->_key, cur->_key); //易错点，找到节点并不知道 if (parent->_left == leftMax) { parent->_left = leftMax->_left; } else { parent->_right = leftMax->_left; } cur = leftMax; } delete cur; return true; } } return false;}迭代
这里面也是指针的引用bool Erase(const K& key){ return _Erase(_root, key);}bool _Erase(Node*& root, const K& key){ if (root == nullptr) return false; if (key < root->_key) { return _Erase(root->_left, key); } else if(key>root->_key) { return _Erase(root->_right, key); } else { Node* del = root; if (root->_left == nullptr) { root = root->_right; } else if (root->_right == nullptr) { root = root->_left; } else { Node* leftMax = root->_left; while (leftMax->_right) { leftMax = leftMax->_right; } swap(root->_key, leftMax->_key); return _Erase(root->_left, key); } delete del; return true; }}BST遍历
直接递归实现 void _InOrder(Node* root){ if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right);}源码
迭代
#pragma oncenamespace MyBST{template<class K>class BSTTree{public:BSTTree<K>* _left;BSTTree<K>* _right;K _key;BSTTree(const K& key): _left(nullptr), _right(nullptr), _key(key){}};template<class K>class BST{typedef BSTTree<K> Node;public:BST():_root(nullptr){}BST(const BST& t){return _Copy(_root);}BST& operator=(const BST& t){swap(_root, t._root);return *this;}~BST(){_destory();}bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}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;}}if (key < parent->_key){parent->_left = new Node(key);}else{parent->_right = new Node(key);}return true;}bool Find(const K& key){if (_root == nullptr)return false;Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return true;}}return false;}bool Erase(const K& key){Node* cur = _root;Node* parent = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{if (cur->_left == nullptr){if (cur == _root){cur = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}else{Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(leftMax->_key, cur->_key);//易错点if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}return false;}void InOrder(){_InOrder(_root);cout << endl;}private:void _destory(Node* root){if(root == nullptr){return;}_destory(root->_left);_destory(root->_right);delete root;root = nullptr;}Node* _Copy(Node* root){Node* copynode = new Node(root->_key);copynode->_left = _Copy(root->_left);copynode->_right = _Copy(root->_right);return copynode;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _root;};}递归
#pragma once#include<iostream>using namespace std;namespace MyBSTR{template<class K>class BSTTree{public:BSTTree<K>* _left;BSTTree<K>* _right;K _key;BSTTree(const K& key): _left(nullptr), _right(nullptr), _key(key){}};template<class K>class BST{typedef BSTTree<K> Node;public:BST():_root(nullptr){}BST(const BST<K>& copy){_root = _copy(copy._root);}BST& operator=(BST t){swap(_root, t.root);return *this;}~BST(){_destory(_root);}bool Insert(const K& key){return _Insert(_root,key);}bool Find(const K& key){return _Find(_root ,key);}bool Erase(const K& key){return _Erase(_root, key);}void InOrder(){_InOrder(_root);cout << endl;}private:void _destory(Node* root){if (root == nullptr)return;_destory(root->_left);_destory(root->_right);delete root;root = nullptr; }Node* _Copy(Node* root){if (root == nullptr)return nullptr;Node* copynode = new Node(root->_key);copynode->_left = _Copy(root->_left);copynode->_right = _Copy(root->_right);return copynode;}bool _Erase(Node*& root, const K& key){if (root == nullptr)return false;if (key < root->_key){return _Erase(root->_left, key);}else if(key>root->_key){return _Erase(root->_right, key);}else{Node* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _Erase(root->_left, key);}delete del;return true;}}bool _Find(Node* root,const K& key){if (root == nullptr)return false;if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return true;}}//插入bool _Insert(Node*& root ,const K& key){if (root == nullptr){root = new Node(key);return true;}if (key < root->_key){return _Insert(root->_left, key);}else if(key > root->_key ){return _Insert(root->_right, key);}else{return false;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _root;};}