概念：
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树
二叉树的插入：
如果插入值比节点值大，就向右继续走，如果插入值比节点值小，就向左继续走
bool Insert(const T&data){if (_root == nullptr){_root = new Node(data);return true;}Node* prev = nullptr;Node* cur = _root;while (cur){if (cur->_data < data) {prev = cur;cur = cur->_right;}else if (cur->_data > data){prev = cur;cur = cur->_left;}else{return false;}}Node* newnode = new Node(data);if (prev->_data>data)//判定值，有点妙{prev->_left =newnode;}else if (prev->_data<data){prev->_right = newnode;}return true;}二叉树的查找：
bool Find(const T& data)
{Node* cur = _root;while (cur){if (cur->_data < data) {cur = cur->_right;}else if (cur->_data > data){cur = cur->_left;}else{return true;}}return false;
}二叉树的删除：
删除情况比较复杂，分三种情况：1.该节点无孩子--直接删除 ，2.该节点有左孩子或者右孩子 ，3. 该节点左右孩子都有
bool Erase(const T& data)
{Node* cur = _root;Node* prev = nullptr;while (cur){if (cur->_data < data) {prev = cur;cur = cur->_right;}else if (cur->_data > data){prev = cur;cur = cur->_left;}else{//左边为空if (cur->_left == nullptr){if (prev == nullptr){_root= cur->_right;}//先判断我是父亲的左还是右else if (prev->_left == cur){prev->_left = cur->_right;}else if (prev->_right == cur){prev->_right = cur->_right;}delete cur;cur = nullptr;}//右边为空else if (cur->_right == nullptr){if (prev == nullptr){_root= cur->_left;}else if (prev->_right == cur){prev->_right = cur->_left;}else if (prev->_left == cur){prev->_left = cur->_left;}delete cur;cur = nullptr;}else//左右子树都不为空，找左子树最大节点或右子树最小节点替代原节点{//找左子树最大节点Node* leftmax = cur->_left;//leftmax肯定不为空Node* leftmaxp = nullptr;while (leftmax->_right){leftmaxp = leftmax;leftmax = leftmax->_right;}cur->_data = leftmax->_data;if (leftmaxp == nullptr){cur->_left = leftmax->_left;return true;}leftmaxp->_right = leftmax->_left;delete leftmax;leftmax = nullptr;}return true;}}return false;
}二叉搜索树的实现：
template<class T>
struct BSNode
{T _data;BSNode* _left;BSNode* _right;BSNode(const T&data=T()):_data(data),_left(nullptr),_right(nullptr){}
};
template<class T>class BSTree
{
public:typedef BSNode<T> Node;BSTree() = default;~BSTree(){Destroy(_root);}BSTree(const BSTree<T>& tree){_root = Copy(tree._root);}bool Insert(const T&data){if (_root == nullptr){_root = new Node(data);return true;}Node* prev = nullptr;Node* cur = _root;while (cur){if (cur->_data < data) {prev = cur;cur = cur->_right;}else if (cur->_data > data){prev = cur;cur = cur->_left;}else{return false;}}Node* newnode = new Node(data);if (prev->_data>data)//判定值，有点妙{prev->_left =newnode;}else if (prev->_data<data){prev->_right = newnode;}return true;}bool Find(const T& data){Node* cur = _root;while (cur){if (cur->_data < data) {cur = cur->_right;}else if (cur->_data > data){cur = cur->_left;}else{return true;}}return false;}bool Erase(const T& data){Node* cur = _root;Node* prev = nullptr;while (cur){if (cur->_data < data) {prev = cur;cur = cur->_right;}else if (cur->_data > data){prev = cur;cur = cur->_left;}else{//左边为空if (cur->_left == nullptr){if (prev == nullptr){_root= cur->_right;}//先判断我是父亲的左还是右else if (prev->_left == cur){prev->_left = cur->_right;}else if (prev->_right == cur){prev->_right = cur->_right;}delete cur;cur = nullptr;}//右边为空else if (cur->_right == nullptr){if (prev == nullptr){_root= cur->_left;}else if (prev->_right == cur){prev->_right = cur->_left;}else if (prev->_left == cur){prev->_left = cur->_left;}delete cur;cur = nullptr;}else//左右子树都不为空，找左子树最大节点或右子树最小节点替代原节点{//找左子树最大节点Node* leftmax = cur->_left;//leftmax肯定不为空Node* leftmaxp = nullptr;while (leftmax->_right){leftmaxp = leftmax;leftmax = leftmax->_right;}cur->_data = leftmax->_data;if (leftmaxp == nullptr){cur->_left = leftmax->_left;return true;}leftmaxp->_right = leftmax->_left;delete leftmax;leftmax = nullptr;}return true;}}return false;}void Inorder(){Inorder1(_root);cout << endl;}
private:void Inorder1(Node*root)//中序遍历{if (root == nullptr){return;}Inorder1(root->_left);cout << root->_data << " ";Inorder1(root->_right);}void Destroy(Node* root){if (root == nullptr){return ;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* newnode = new Node(root->_data);newnode->_left = Copy(root->_left);newnode->_right = Copy(root->_right);return newnode;}Node* _root=nullptr;
};