一。定义：二叉搜索树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 任意节点的左、右也分别为二叉查找树。

4. 没有键值相等的节点（no duplicate nodes）。

根据二叉搜索树的特点知：对二叉搜索树进行中序遍历得到的结点序列必然是一个有序序列。

一棵二叉搜索树：

根据树的结构，我们可以封装一个结点的结构BSNode：

template<classK,classV>structBSNode{BSNode<K,V>*_left;BSNode<K,V>*_right;K_key;V_value;BSNode(constK&key,constV&value):_left(NULL),_right(NULL),_key(key),_value(value){}};

在这里树的结构封装了key/value形式的键值对。

二叉搜索树的结构我们更加关注的是它的增删查改功能。而且在这过程中我们要保证整棵树中没有重复的key值（结点的值）

所以封装一棵二叉搜索树BSTree：

template<classK,classV>classBSTree{public:typedefBSNode<K,V>Node;<prename="code"class="cpp">//增删改查功能protected:Node*_root;};

二。实现

(一）插入新结点

boolInsert(constK&key,constV&value)//<span>非递归形式</span>{if(_root==NULL){_root=newNode(key,value);returntrue;}Node*parent=NULL;Node*cur=_root;while(cur){if(cur->_key>key){parent=cur;cur=cur->_left;}elseif(cur->_key<key){parent=cur;cur=cur->_right;}elsereturnfalse;}if(parent->_left==NULL&&parent->_key>key){parent->_left=newNode(key,value);}elseif(parent->_right==NULL&&parent->_key<key){parent->_right=newNode(key,value);}returntrue;}

boolInsert_R(constK&key,constV&value)//<span>插入的递归实现</span>{return_Insert_R(_root,key,value);}</span><prename="code"class="cpp">bool_Insert_R(Node*&root,constK&key,constV&value){if(root==NULL){root=newNode(key,value);returntrue;}if(root->_key>key)_Insert_R(root->_left,key,value);elseif(root->_key<key)_Insert_R(root->_right,key,value);elsereturnfalse;returnfalse;}

插入节点的思路就是递归的找要插入的位置，直到root为NULL，那么当前位置就是要插入的位置。

（二）查找结点，返回该结点

Node*Find(constK&key)//<span>非递归实现</span>{Node*cur=_root;while(cur){if(cur->_key>key){cur=cur->_left;}elseif(cur->_key<key){cur=cur->_right;}elsereturncur;}returnNULL;}

Node*Find_R(constK&key)//<span>递归实现</span>{return_Find_R(_root,key);}<prename="code"class="cpp">Node*_Find_R(Node*root,constK&key){if(root==NULL)returnNULL;if(root->_key>key)_Find_R(root->_left,key);elseif(root->_key<key)_Find_R(root->_right,key);elsereturnroot;}

查找的实现就是分三种情况，当前结点key大于key，小于key，等于key。大于key递归的在当前结点的右子树查找，小于在左子树找，等于就返回结点。

（三）删除结点，使剩下结点仍是一棵二叉搜索树

boolRemove(constK&key)//非递归实现{return_Remove(_root,key);}

bool_Remove(Node*root,constK&key){if(root==NULL)returnfalse;Node*parent=NULL;Node*cur=root;Node*del=NULL;while(cur){if(cur->_key>key){parent=cur;cur=cur->_left;}elseif(cur->_key<key){parent=cur;cur=cur->_right;}else{del=cur;//待删除结点左为空if(cur->_left==NULL){if(parent&&parent->_left==cur)parent->_left=cur->_right;elseif(parent&&parent->_right==cur)parent->_right=cur->_right;else_root=cur->_right;}elseif(cur->_right==NULL)//待删除结点右为空{if(parent&&parent->_left==cur)parent->_left=cur->_left;elseif(parent&&parent->_right==cur)parent->_right=cur->_left;else_root=cur->_left;}elseif(cur->_left==NULL&&cur->_right==NULL)//待删除结点左右都为空{if(parent&&parent->_left==cur)parent->_left=NULL;elseif(parent&&parent->_right==cur)parent->_right=NULL;else_root=NULL;}elseif(cur->_left&&cur->_right)//待删除结点左右都不为空{//找出右子树的最左结点Node*firstleft=cur->_right;parent=cur;while(firstleft->_left){parent=firstleft;firstleft=firstleft->_left;}del=firstleft;swap(cur->_key,firstleft->_key);swap(cur->_value,firstleft->_value);//判断最左结点是它父节点的左结点还是右结点if(parent&&parent->_left==firstleft){parent->_left=firstleft->_right;}elseif(parent&&parent->_right==firstleft){parent->_right=firstleft->_right;}else//parent==NULL。待删除结点的右边只有一个结点，则最左结点就是它{root->_right=NULL;}}deletedel;returntrue;}}returnfalse;}

boolRemove_R(constK&key)//递归实现{return_Remove_R(_root,key);}<prename="code"class="cpp">bool_Remove_R(Node*&root,constK&key){if(root==NULL)returnfalse;if(root->_key>key){_Remove_R(root->_left,key);}elseif(root->_key<key){_Remove_R(root->_right,key);}else{Node*del=root;if(root->_left==NULL&&root->_right==NULL){root=NULL;}elseif(root->_left==NULL){root=root->_right;}elseif(root->_right==NULL){root=root->_left;}else{Node*parent=NULL;Node*firstleft=root->_right;while(firstleft->_left){parent=firstleft;firstleft=firstleft->_left;}del=firstleft;swap(root->_key,firstleft->_key);swap(root->_value,firstleft->_value);if(parent&&parent->_left==firstleft){parent->_left=firstleft->_right;}elseif(parent&&parent->_right==firstleft){parent->_right=firstleft->_right;}else//parent==NULL。待删除结点的右边只有一个结点，则最左结点就是它{root->_right=NULL;}}deletedel;returntrue;}returnfalse;}

删除节点要考虑到的因素就要多了。我们可以划分子问题的方法来解决：

查找待删除的结点，每次判断：

当前结点key值大于key。递归进入左子树，继续查找。

当前结点key值小于key。递归进入右子树，继续查找。

当前结点key值等于key。在这又分为4种情况：

当前结点的左子树为空。删除当前结点，把右子树给当前指针

当前结点的右子树为空。删除当前结点，把左子树给当前指针

当前结点的左右子树都为空。把根指针置空，删除当前结点。

当前结点的左右子树都不为空。找到右子树的最左结点，和待删除结点交换值，删除最左结点。

把这些因素都考虑周全就可以准确的删除二叉搜索树的任何一个结点。