二叉查找树（Binary Search Tree）,也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一颗空树或者具有下列性质的二叉树：

（1）每个节点都有一个作为搜索依据的关键码（key），所有的节点的关键码互不相同。

（2）左子树上所有的关键码（key）都小于根节点点的关键码（key）。

（3）右子树上所有的关键码（key）都大于根节点的关键码（key）。

（4）左右子树都是二叉搜索树。

代码实现如下：

#include<iostream>usingnamespacestd;template<classK,classV>structBSTreeNode{BSTreeNode<K,V>*_left;BSTreeNode<K,V>*_right;K_key;V_value;BSTreeNode(constK&key,constV&value):_key(key),_value(value),_left(NULL),_right(NULL){}};template<classK,classV>classBSTree{typedefBSTreeNode<K,V>Node;public:BSTree():_root(NULL){}//非递归boolInsert(constK&key,constV&value){if(_root==NULL){_root=newNode(key,value);returntrue;}Node*parent=_root;Node*cur=_root;while(cur){if(cur->_key>key){parent=cur;cur=cur->_left;}elseif(cur->_key<key){parent=cur;cur=cur->_right;}else{returnfalse;}}if(parent->_key>key){parent->_left=newNode(key,value);}else{parent->_right=newNode(key,value);}returntrue;}voidInOrder(){_InOrder(_root);cout<<endl;}Node*Find(constK&key){if(_root==NULL){returnNULL;}Node*cur=_root;while(cur){if(cur->_key>key){cur=cur->_left;}elseif(cur->_key<key){cur=cur->_right;}else{returncur;}}returnNULL;}boolRemove(constK&key){if(_root==NULL){returnfalse;}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;}elsebreak;}if(cur==NULL)returnfalse;Node*del;//删除节点的左为空if(cur->_left==NULL){del=cur;if(parent==NULL){_root=cur->_right;}else{if(parent->_left==cur){parent->_left=cur->_right;}else{parent->_right=cur->_right;}}deletedel;}//删除节点的右为空elseif(cur->_right==NULL){del=cur;if(parent==NULL){_root=cur->_left;}else{if(parent->_left==cur){parent->_left=cur->_left;}else{parent->_right=cur->_left;}}deletedel;}//删除节点的左右都不为空else{//找右树的最左节点，也就是右边最小的数parent=cur;Node*left=cur->_right;while(left->_left){parent=left;left=left->_left;}del=left;cur->_key=left->_key;cur->_value=left->_value;if(parent->_left==left){parent->_left=left->_right;}else{parent->_right=left->_right;}deletedel;}returntrue;}//递归Node*FindR(constK&key){return_FindR(_root,key);}boolInsertR(constK&key,constV&value){return_InsertR(_root,key,value);}boolRemoveR(constK&key){return_RemoveR(_root,key);}protected:void_InOrder(Node*root){if(root!=NULL){_InOrder(root->_left);cout<<root->_key<<"";_InOrder(root->_right);}}Node*_FindR(Node*root,constK&key){if(root==NULL){returnNULL;}if(root->_key==key){returnroot;}if(root->_key>key){return_FindR(root->_left,key);}else{return_FindR(root->_right,key);}returnNULL;}bool_InsertR(Node*&root,constK&key,constV&value){if(root==NULL){root=newNode(key,value);returntrue;}if(root->_key>key){return_InsertR(root->_left,key,value);}else{return_InsertR(root->_right,key,value);}returnfalse;}bool_RemoveR(Node*&root,constK&key){if(root==NULL){returnfalse;}if(root->_key>key){return_RemoveR(root->_left,key);}elseif(root->_key<key){return_RemoveR(root->_right,key);}else{//删除的节点的左为空if(root->_left==NULL){root=root->_right;}//删除节点的右为空elseif(root->_right==NULL){root=root->_left;}else{//找右边最左的节点（即右边最小的节点）替换删除的该节点（下面程序采用的）。//或者找左边最右的节点（即左边最大的节点）替换删除的该节点Node*parent=root;Node*left=root->_right;while(left->_left){parent=left;left=left->_left;}root->_key=left->_key;root->_value=left->_value;if(parent->_left==left){parent->_left=left->_right;}else{parent->_right=left->_right;}}returntrue;}returnfalse;}protected:Node*_root;};#include"BSTree.h"voidTest1(){intarr[10]={0,1,3,5,4,2,7,8,6,9};BSTree<int,int>bst;for(inti=0;i<sizeof(arr)/sizeof(arr[0]);++i){bst.Insert(arr[i],i);}bst.InOrder();BSTreeNode<int,int>*ret1=bst.Find(8);if(ret1){cout<<ret1->_key<<":"<<ret1->_value<<endl;}elsecout<<"没有找到ret1"<<endl;BSTreeNode<int,int>*ret2=bst.Find(22);if(ret2){cout<<ret2->_key<<":"<<ret2->_value<<endl;}elsecout<<"没有找到ret2"<<endl;bst.Remove(9);bst.Remove(7);bst.Remove(8);bst.InOrder();bst.Remove(0);bst.Remove(1);bst.Remove(2);bst.Remove(3);bst.Remove(4);bst.Remove(5);bst.Remove(6);bst.Remove(7);bst.Remove(8);bst.Remove(9);bst.InOrder();}voidTest2(){intarr[10]={0,1,3,5,4,2,7,8,6,9};BSTree<int,int>bst;for(inti=0;i<sizeof(arr)/sizeof(arr[0]);++i){bst.InsertR(arr[i],i);}bst.InOrder();BSTreeNode<int,int>*ret1=bst.Find(7);if(ret1){cout<<ret1->_key<<":"<<ret1->_value<<endl;}elsecout<<"没有找到ret1"<<endl;BSTreeNode<int,int>*ret2=bst.Find(12);if(ret2){cout<<ret2->_key<<":"<<ret2->_value<<endl;}elsecout<<"没有找到ret2"<<endl;bst.RemoveR(8);bst.RemoveR(7);cout<<bst.RemoveR(9)<<endl;bst.InOrder();bst.RemoveR(0);bst.RemoveR(1);cout<<bst.RemoveR(2)<<endl;bst.RemoveR(3);bst.RemoveR(4);bst.RemoveR(5);bst.RemoveR(6);bst.RemoveR(7);cout<<bst.RemoveR(8)<<endl;bst.RemoveR(9);bst.InOrder();}intmain(){Test1();Test2();return0;}

运行结果：