二叉搜索树：

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

2.左子树的所有关键码都小于根节点的关键码。

3.右子树的所有关键码都大于根节点的关键码。

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

删除key：左为空，右为空，左右都不空

1）左为空：cur的右树链到父节点

2）右为空：cur的左树链到父节点

3）左右都不空：找右树最左节点或左树最右节点，将找到的节点与cur交换后删除它。

二叉搜索树的增、删、查（非递归及递归）程序代码如下：

#pragmaonce#include<string>////注意：考虑边界问题_root、左右子树问题（非递归、递归）、记住判空处理template<classK,classV>structBSTNode{BSTNode<K,V>*_left;//左子数BSTNode<K,V>*_right;//右子树K_key;V_value;//构造函数BSTNode(constK&key,constV&value):_left(NULL),_right(NULL),_key(key),_value(value){}};template<classK,classV>classBSTree{typedefBSTNode<K,V>Node;public:BSTree():_root(NULL){}public://boolInsert(constK&key,constV&value);//boolRemove(constK&key);//Node*Find(constK&key);//boolInsert_R(constK&key,constV&value);//boolRemove_R(constK&key,constV&value);//Node*Find_R(constK&key);boolInsert(constK&key,constV&value){if(_root==NULL)_root=newNode(key,value);Node*cur=_root;while(cur){if(key<cur->_key)//key小，插入左子树{if(cur->_left==NULL)cur->_left=newNode(key,value);elsecur=cur->_left;}elseif(key>cur->_key)//key大，插入右子树{if(cur->_right==NULL)cur->_right=newNode(key,value);elsecur=cur->_right;}else//key关键码互不相同returnfalse;}returntrue;}////////////////删除//////////////////边界条件判断（无节点，一个节点）////找key值，记录parent。////删除key，分三种情况(左为空，右为空，左右都不为空)////左右节点都存在，找到右树的最左节点或者左树的最右节点，////将找到的节点与cur交换后再删除找到的节点boolRemove(constK&key){//无节点if(_root==NULL)returnfalse;//一个节点_rootif(_root->_left==NULL&&_root->_right==NULL){if(key==_root->_key){delete_root;_root=NULL;returntrue;}elsereturnfalse;}Node*cur=_root;Node*parent=NULL;while(cur){//找key值，记录parentif(key<cur->_key){parent=cur;cur=cur->_left;}elseif(key>cur->_key){parent=cur;cur=cur->_right;}////删除key，分三种情况(左为空，右为空，左右都不为空)else{Node*del=cur;if(cur->_left==NULL)//将cur的右子树链到父节点{//注意parent可能为空if(parent==NULL){_root=cur->_right;}else{if(cur=parent->_left)parent->_left=cur->_right;elseparent->_right=cur->_right;}}elseif(cur->_right==NULL)//将cur的左子树链到父节点{if(parent==NULL){_root=cur->_left;}else{if(cur=parent->_left)parent->_left=cur->_left;elseparent->_right=cur->_left;}}////左右节点都存在，找到右树的最左节点或者左树的最右节点////将找到的节点与cur交换后再删除找到的节点else{parent=cur;//右树的最左节点firstLeftNode*firstLeft=cur->_right;while(firstLeft->_left){parent=firstLeft;firstLeft=firstLeft->_left;}swap(firstLeft->_key,cur->_key);swap(firstLeft->_value,cur->_value);del=firstLeft;//因为左右节点都存在，所以parent不为空//firstLeft左节点为空，右节点可能存在if(firstLeft==parent->_left)parent->_left=firstLeft->_right;elseparent->_right=firstLeft->_right;}/*找到firstLeft代替del*/deletedel;returntrue;}}//whileendreturnfalse;}//查找Node*Find(constK&key){if(_root==NULL)returnNULL;Node*cur=_root;while(cur){if(key<cur->_key)//在左子树查找{cur=cur->_left;}elseif(key>cur->_key)//在右子树查找{cur=cur->_right;}else{returncur;}}returnNULL;}/////////////////////递归实现增删查boolInsert_R(constK&key,constV&value){return_Insert_R(_root,key,value);}boolRemove_R(constK&key){return_Remove_R(_root,key);}Node*Find_R(constK&key){return_Find_R(_root,key);}//中序遍历voidInOrder(){return_InOrder(_root);}boolEmpty(){if(_root==NULL){returntrue;}returnfalse;}protected:void_InOrder(Node*root){if(root==NULL)return;_InOrder(root->_left);//cout<<root->_key<<""<<endl;cout<<"key:"<<root->_key<<",value:"<<root->_value<<endl;_InOrder(root->_right);}////注意：root参数应为引用&每次递归的root即为上一次的root->_left或者root->_rightbool_Insert_R(Node*&root,constK&key,constV&value){if(root==NULL){root=newNode(key,value);returntrue;}if(key<root->_key){return_Insert_R(root->_left,key,value);}elseif(key>root->_key){return_Insert_R(root->_right,key,value);}else{returnfalse;}}//查找Node*_Find_R(Node*&root,constK&key){if(root==NULL)returnNULL;if(key<root->_key){return_Find_R(root->_left,key);}elseif(key>root->_key){return_Find_R(root->_right,key);}else{returnroot;}}//删除bool_Remove_R(Node*&root,constK&key){if(root==NULL)returnfalse;if(key<root->_key){return_Remove_R(root->_left,key);}elseif(key>root->_key){return_Remove_R(root->_right,key);}///删除key////以引用root作参数，root相当于上一层的root->_left或者root->_rightelse{Node*del=root;if(root->_left==NULL){root=root->_right;deletedel;returntrue;}elseif(root->_right==NULL){root=root->_left;deletedel;returntrue;}///左右节点都不为空else{//右子树的最左节点Node*firstLeft=root->_right;while(firstLeft->_left){firstLeft=firstLeft->_left;}swap(firstLeft->_key,root->_key);swap(firstLeft->_value,root->_value);//_Remove_R(firstLeft,key);//错误，firstLeft是临时变量不能作为递归的参数_Remove_R(root->_right,key);}}///删除keyendreturnfalse;}protected:Node*_root;};

测试代码：

voidTestBSTree(){BSTree<int,int>bst;bst.Insert(5,1);bst.Insert(3,1);bst.Insert(4,1);bst.Insert(1,1);bst.Insert(7,1);bst.Insert(8,1);bst.Insert(2,1);bst.Insert(6,1);bst.Insert(0,1);bst.Insert(9,1);bst.InOrder();cout<<"?"<<bst.Find(1)->_key<<endl;cout<<"?"<<bst.Find(8)->_key<<endl;cout<<"?"<<bst.Find(22)<<endl;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.Remove(0);if(bst.Empty())cout<<"此二叉搜索树为空"<<endl;bst.InOrder();}voidTestBSTree_R()//递归{BSTree<int,int>bst;bst.Insert_R(5,1);bst.Insert_R(3,1);bst.Insert_R(4,1);bst.Insert_R(1,1);bst.Insert_R(7,1);bst.Insert_R(8,1);bst.Insert_R(2,1);bst.Insert_R(6,1);bst.Insert_R(0,1);bst.Insert_R(9,1);bst.InOrder();cout<<"?"<<bst.Find(1)->_key<<endl;cout<<"?"<<bst.Find(8)->_key<<endl;cout<<"?"<<bst.Find(22)<<endl;/*bst.Remove_R(1);bst.Remove_R(2);bst.Remove_R(3);bst.Remove_R(4);*/bst.Remove_R(5);bst.Remove_R(6);bst.Remove_R(7);bst.Remove_R(8);bst.Remove_R(9);bst.Remove_R(0);if(bst.Empty())cout<<"此二叉搜索树为空"<<endl;bst.InOrder();}voidTestBSTree_string()//intstring{BSTree<int,string>bst;bst.Insert(5,"zhou");bst.Insert(3,"sun");bst.Insert(4,"li");bst.Insert(1,"zhao");bst.Insert(7,"zheng");bst.Insert(8,"wang");bst.Insert(2,"qian");bst.Insert(6,"wu");bst.Insert(0,"baijiaxing");bst.Insert(9,"feng");bst.InOrder();cout<<"?"<<bst.Find(1)->_key<<endl;cout<<"?"<<bst.Find(8)->_key<<endl;cout<<"?"<<bst.Find(22)<<endl;//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);if(bst.Empty())cout<<"此二叉搜索树为空"<<endl;bst.InOrder();}