这篇博客要说的是二叉搜索树，又叫二叉排序树，它或者是一颗空树，或者是具有以下性质的二叉树：

·若它的左子树不为空，那么左子树上所有节点的值都小于根节点的值，不会出现等于的情况

·若它的右子树不为空，那么右子树上所有节点的值都大于根节点的值，不会出现等于的情况

·它的左右子树也分别为二叉搜索树

我们可以由上边的特点推断出二叉树的中序遍历是有序的，比如给一个二叉搜索树

中序遍历就是7 15 17 22 27 30 45 60 75这是有序的。

知道了它的这些特性，那么我们来自己来模拟实现一下：

我们首先需要一个节点的类

然后我们写一个查找函数，就是根据我们上边的规则进行查找

下面我们写一个插入元素的函数，我们在插入的时候，一味的找底为空是不行的，我们需要记录下它的父亲的节点才可以

此时我们就可以创建一个二叉搜索树，那么我按中序遍历试一试，究竟是不是有序的呢？我们就写一个中序遍历的打印函数，我们在调用函数的时候是不需要传值的，而递归打印又需要根节点的值，所以我们封装一层

下面就是我们删除节点的函数，删除的节点有三种情况，没有孩子，有一个孩子和有两个孩子。其中没有孩子和有一个孩子可以一起处理，就是有两个孩子的比较难处理，我们选择用替换法：就是用左子树中最大节点或右子树中最小节点去替换掉我们要删除的值。大家可以想一想为什么，因为我这样替换并不影响搜索二叉树的性质。由于代码比较长，我们放在文章的最后

下面我们来递归实现以下查找和插入函数，跟我们的打印一样，我们要实现递归就要封装一层，我们先来实现简单的插入和查找

注意了：_insertR这里第一个参数我们用的引用，如果不用引用的话，那么root就只是一个拷贝，并不会对实际的二叉树产生影响。下面是删除函数的递归形式

那如果我们想用一棵二叉树生成另一颗二叉树，我们就要写拷贝构造，因为默认生成的是浅拷贝，以及后面一系列的析构和赋值重载

上面就是我们的类的一系列函数下面有两个模型，一个叫key模型，一个叫keyvalue模型，key搜索模型就是快速查找一个值是否存在，比如我们的门禁系统，小区车库都是根据你的信息，去系统中查找这个值是否存在。keyvalue模型是通过一个值去查找另一个值是否存在，比如说：商场车库，通过车牌号去查找你的停车时间，比如手机上的词典软件，高铁站刷票系统，通过你的信息去查找这辆列车有没有你的信息。

下面是所有的代码

template<class K>
struct BSTreeNode {
	BSTreeNode(const K& key)
		:left(nullptr)
		,right(nullptr)
		,_key(key){}
	BSTreeNode(){}
	BSTreeNode* left=nullptr;
	BSTreeNode* right=nullptr;
	K _key=K();
};

template<class K>
class BSTree {
	typedef BSTreeNode<K> Node;
public:
	bool find(const K& key) {
		if (_root == nullptr) {
			return false;
		}
		Node* cur = _root;
		while (cur != nullptr) {
			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* tmp = new Node(key);
		//tmp->_key = key;
		if (_root == nullptr) {
			_root = tmp;
			return true;
		}
		else {
			Node* cur = _root;
			Node* parent = _root;
			while (cur != nullptr) {
				if (cur->_key < key) {
					parent = cur;
					cur = cur->right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->left;
				}
				else return false;
			}
			if (parent->_key < key)parent->right = tmp;
			else if (parent->_key > key)parent->left = tmp;
			return true;
		}
	}
	bool erase(const K& key) {
		if (_root == nullptr)return false;
		else {
			Node* cur = _root;
			Node* parent = _root;
			while (cur != nullptr) {
				if (cur->_key < key) {
					parent = cur;
					cur = cur->right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->left;
				}
				else {
						if (cur->left == nullptr) {
							if (parent->left == cur) {
								parent->left = cur->right;
							}
							else if (parent->right == cur) {
								parent->right = cur->right;
							}
							else {
								Node* tmp = _root;
								_root = _root->right;
							}
							delete cur;
							return true;
						}
						else if(cur->right==nullptr) {
							if (parent->left == cur) {
								parent->left = cur->left;
							}
							else if (parent->right == cur) {
								parent->right = cur->left;
							}
							else {
								Node* tmp = _root;
								_root = _root->left;
							}
							delete cur;
							return true;
						}
					else {
						Node* leftreemax = cur->left;
						Node* leftreemaxpa = cur;
						while (leftreemax->right != nullptr) {
							leftreemaxpa = leftreemax;
							leftreemax = leftreemax->right;
						}
						cur->_key = leftreemax->_key;
						leftreemaxpa->left = leftreemax->left;
						delete leftreemax;
						return true;
					}
				}
			}
			return false;
		}
	}
								
	

	void PrintBSTree() {
		_PrintBSTree(_root);
		cout << endl;
	}
	bool findR(const K& key) {
		return _findR(_root, key);
	}
	bool insertR(const K& key) {
		return _insertR(_root, key);
	}
	bool eraseR(const K& key) {
		return _eraseR(_root, key);
	}
	~BSTree() {
		Destroy(_root);
	}
	BSTree() = default;//强制生成默认构造
	BSTree(const BSTree<K>& t) {
		_root=copy(t._root);
	}
	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}
private:
	Node* copy(Node* root) {
		if (root == nullptr)return nullptr;
		Node* newnode = new Node(root->_key);
		newnode->left = copy(root->left);
		newnode->right = copy(root->right);
		return newnode;
	}

	void Destroy(Node* root) {
		if (root == nullptr)return;
		Destroy(root->left);
		Destroy(root->right);
		delete root;
	}

	bool _eraseR(Node*& root, const K& key) {
		if (root == nullptr)return false;
		if (root->_key < key) {
			return _eraseR(root->right, key);
		}
		else if (root->_key > key) {
			return _eraseR(root->left, key);
		}
		else {
			if (root->left == nullptr) {
				Node* tmp = root;
				root = root->right;
				delete tmp;
				return true;
			}
			else if (root->right == nullptr) {
				Node* tmp = root;
				root = root->left;
				delete tmp;
				return true;
			}
			else {
				Node* leftreemaxpa = root;
				Node* leftreemax = root->left;
				while (leftreemax->right != nullptr) {
					leftreemaxpa = leftreemax;
					leftreemax = leftreemax->right;
					}
					swap(root->_key, leftreemax->_key);
					return _eraseR(root->left, key);
					/*root->_key = leftreemax->_key;
					if (leftreemax == leftreemaxpa->left)leftreemaxpa->left = leftreemax->left;
					else leftreemaxpa->right = leftreemax->left;
					delete leftreemax;
					return true;*/
				}
			}
		}
	

	bool _insertR(Node*& root, const K& key) {
		if (root == nullptr) {
			root = new Node(key);
			return true;
		}
		if (root->_key < key) {
			return _insertR(root->right, key);
		}
		else if (root->_key > key) {
			return _insertR(root->left, key);
		}
		else return false;
	}

	bool _findR(Node* root, const K& key) {
		if (root == nullptr)return false;
		if (root->_key == key)return true;
		else if (root->_key < key)return _findR(root->right, key);
		else return _findR(root->left, key);
	}

	void _PrintBSTree(Node* root) {
		if (root == nullptr) return;
		_PrintBSTree(root->left);
		cout << root->_key << ' ';
		_PrintBSTree(root->right);
	}
	Node* _root=nullptr;
};