#pragmaonce#include<iostream>usingnamespacestd;template<classK,classV>structBsTreeNode{//二叉树节点K_key;V_value;BsTreeNode*_left;BsTreeNode*_right;BsTreeNode(constK&key,constV&value):_key(key),_value(value),_left(NULL),_right(NULL){}};template<classK,classV>classBsTree{public:typedefBsTreeNode<K,V>Node;BsTree():_root(NULL){}~BsTree(){}boolInsert(constK&key,constV&value)//插入非递归{if(_root==NULL){_root=newNode(key,value);returntrue;}Node*cur=_root;while(1){if(cur->_key>key){if(cur->_left)cur=cur->_left;else{cur->_left=newNode(key,value);returntrue;}}elseif(cur->_key<key){if(cur->_right)cur=cur->_right;else{cur->_right=newNode(key,value);returntrue;}}//以上为找插入位置并插入elseif(cur->_key==key)//存在插入失败returnfalse;}}boolInsertR(constK&key,constV&value)//插入递归{return_InsertR(_root,key,value);}Node*Find(constK&key){//查找Node*cur=_root;while(cur){if(cur->_key>key)cur=cur->_left;elseif(cur->_key<key)cur=cur->_right;elsereturncur;}returnNULL;}boolRemoveR(constK&key)//删除递归{if(_root==NULL)returnfalse;return_RemoveR(_root,key);}boolRemove(Kkey){//删除非递归Node*cur=_root,*prev=NULL;while(cur){if(cur->_key>key){prev=cur;cur=cur->_left;}elseif(cur->_key<key){prev=cur;cur=cur->_right;}//以上为找到要删除的节点else{if(cur->_left==NULL)//如果节点左或右为空，直接删除该节//点将之后的节点连接在其父节点{if(prev==NULL){_root=cur->_right;}elseif(prev->_left==cur){prev->_left=cur->_right;}elseprev->_right=cur->_right;}elseif(cur->_right==NULL)//同上右为空{if(prev==NULL){_root=cur->_left;deletecur;}elseif(prev->_right==cur){prev->_right=cur->_left;}elseprev->_left=cur->_left;}else//如果左右都不为空找右孩子最左或左孩子最右节点替//代删除{prev=cur;cur=cur->_right;while(cur->_left){cur=cur->_left;}prev->_key=cur->_key;prev->_value=cur->_value;prev->_right=cur->_right;}deletecur;returntrue;}}returnfalse;}boolmodification(Kkey,Vvalue){//修改Node*ret=Find(key);if(ret==NULL)returnfalse;ret->_value=value;returntrue;}private:bool_InsertR(Node*&root,constK&key,constV&value)//插入递归函数{if(root==NULL){root=newNode(key,value);returntrue;}if(root->_key==key)returnfalse;elseif(root->_key>key)return_InsertR(root->_left,key,value);elsereturn_InsertR(root->_right,key,value);}bool_RemoveR(Node*&root,constK&key)//删除递归函数{if(root->_key<key)return_RemoveR(root->_right,key);if(root->_key>key)return_RemoveR(root->_left,key);if(root->_left==NULL){Node*dev=root;root=root->_right;deletedev;returntrue;}elseif(root->_right==NULL){Node*dev=root;root=root->_left;deletedev;returntrue;}else{root->_key=root->_right->_key;root->_value=root->_right->_value;return_RemoveR(root->_right,root->_key);}}Node*_root;};