● 二叉搜索树满足以下条件的二叉树：
1、每个节点都有一个作为搜索依据的关键码（key），所有节点的关键码互不相同。
2、左子树上所有节点的关键码（key）都小于根节点的关键码（key）。
3、右子树上所有节点的关键码（key）都大于根节点的关键码（key）。
4、左右子树都是二叉搜索树。

● 二叉搜索树的插入过程如下：

1、若当前的二叉搜索树为空，则插入的元素为根节点。

2、若插入的元素值小于根节点值，则将元素插入到左子树中。

3、若插入的元素值大于根节点值，则将元素插入到右子树中。

4、找到插入的位置和插入的位置的父结点，进行链接。

template<classT>voidBSTree<T>::Insert(constT&key,constT&value)//非递归算法进行插入{if(_root==NULL){_root=newNode(key,value);return;}Node*prev=NULL;Node*cur=_root;while(cur)//在树中找到插入的位置{if(key<cur->_key){prev=cur;cur=cur->_left;}elseif(key>cur->_key){prev=cur;cur=cur->_right;}}cur=newNode(key,value);//建立新结点，并判断具体位置进行链接if(prev->_key>cur->_key){prev->_left=cur;}if(prev->_key<cur->_key){prev->_right=cur;}}template<classT>voidBSTree<T>::Insert_R(constT&key,constT&value)//递归算法进行插入{_insert_r(_root,key,value);}template<classT>voidBSTree<T>::_insert_r(Node*&root,constT&key,constT&value)//递归{if(root==NULL)//root为空时，开辟新结点{root=newNode(key,value);return;}Node*cur=root;if(key<cur->_key)_insert_r(cur->_left,key,value);if(key>cur->_key)_insert_r(cur->_right,key,value);}

● 二叉搜索树的查找过程如下：

1、若当前的二叉搜索树为空，则结束函数。

2、若查找的元素值小于根节点值，则在当前结点的左子树中查找。

3、若查找的元素值大于根节点值，则在当前结点的右子树中查找。

template<classT>BSTNode<T>*BSTree<T>::Find(constT&key)//非递归算法进行查找{Node*cur=_root;while(cur){if(key<cur->_key){cur=cur->_left;}elseif(key>cur->_key){cur=cur->_right;}else{returncur;}}returnNULL;}template<classT>BSTNode<T>*BSTree<T>::Find_R(constT&key)//递归{return_find_r(_root,key);}template<classT>BSTNode<T>*BSTree<T>::_find_r(Node*&root,constT&key)//递归算法进行查找{if(root==NULL)//root为空时为没找到{returnNULL;}if(key<root->_key)return_find_r(root->_left,key);elseif(key>root->_key)return_find_r(root->_right,key);elsereturnroot;}

● 二叉搜索树的删除，分两种情况进行处理：

1、找到要删除的结点cur和cur的父亲结点prev。

2、情况一：cur只有一个子树或没有子树。首先考虑删除的结点为根结点时，直接_root指向它的子树；

再考虑cur的左为空、右为空还是左右都为空，进行删除，链接。

3、情况二：cur左右子树都不为空。首先找到cur右子树的最左下结点del，然后进行交换，通过替换法删除del，并使prev的指向置空。

template<classT>voidBSTree<T>::Remove(constT&key)//非递归算法进行删除{if(_root==NULL){return;}Node*prev=NULL;Node*cur=_root;while(cur)//找到要删除的结点cur{if(key<cur->_key){prev=cur;cur=cur->_left;}elseif(key>cur->_key){prev=cur;cur=cur->_right;}elsebreak;}//情况一：cur只有一个孩子或没有孩子，注意考虑cur为根结点时,prev=NULLif(cur->_left==NULL||cur->_right==NULL){if(cur->_left==NULL)//cur只有右孩子{if(prev==NULL)//cur为根结点时_root=cur->_right;elseif(prev->_left==cur)prev->_left=cur->_right;elseprev->_right=cur->_right;}elseif(cur->_right==NULL)//cur只有左孩子{if(prev==NULL)//cur为根结点时_root=cur->_left;elseif(prev->_left==cur)prev->_left=cur->_left;elseprev->_right=cur->_left;}//删除cur并置空，包含了cur的左右为空的情况deletecur;cur=NULL;}//情况二：cur有左右子树,替换法删除else{//先找到cur结点右子树的最左下结点delNode*del=cur;prev=del;del=del->_right;while(del->_left){prev=del;del=del->_left;}//替换法，删除结点del,注意使prev的指向置空swap(cur->_key,del->_key);swap(cur->_value,del->_value);if(prev->_left==del)prev->_left=NULL;elseif(prev->_right==del)prev->_right=NULL;deletedel;del=NULL;}}template<classT>voidBSTree<T>::Remove_R(constT&key)//递归算法进行删除{_remove_r(_root,key);}template<classT>voidBSTree<T>::_remove_r(Node*&root,constT&key)//递归{if(_root==NULL){return;}if(key<root->_key)_remove_r(root->_left,key);elseif(key>root->_key)_remove_r(root->_right,key);else{//情况一：只有一个子树或没有,直接使root重新赋值if(root->_left==NULL||root->_right==NULL){Node*del=root;if(root->_left==NULL)root=root->_right;elseif(root->_right==NULL)root=root->_left;elseroot=NULL;deletedel;del=NULL;}else//情况二：左右子树都不为空{Node*cur=root->_right;//root右子树最左下结点，交换两个结点的值while(cur->_left){cur=cur->_left;}swap(root->_key,cur->_key);swap(root->_value,cur->_value);_remove_r(root->_right,key);//在root的右子树上删除key，转换成情况一中左子树一定为空}}}