‘二叉树’是数据结构中比较重要的一部分，这里主要讨论一下‘搜索二叉树’，针对‘搜索二叉树的插入、删除和查找节点进行分情况讨论，希望能够帮助读者更加的理解搜索二叉树的原理。

◆搜索二叉树的性质：

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

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

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

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

实现‘搜索二叉树’的节点结构可以实现为K形式，和K、V形式，若实现K形式，则K表示节点的值，同时可以使用K来确定节点的位置，若实现K、V形式，则K表示节点的一个标记，用来判断节点在二叉树中具体的存储位置，V表示节点的具体存储的值。这里实现的是K、V形式，K形式读者可以下去自己进行尝试。

◆下面为实现‘搜索二叉树’的具体节点结构：

template<classK,classV>structBSTNode{BSTNode<K,V>*_left;//指向左节点的指针BSTNode<K,V>*_right;//指向右节点的指针K_key;//节点标记，确定节点位置V_value;//节点的值BSTNode(constK&key,constV&value)//构造节点:_key(key),_value(value),_left(NULL),_right(NULL){}};

◆讨论相关操作情况

（1）节点插入

（2）节点删除

（3）节点查找

根据搜索二叉树的性质来进行查找，当key>root->key;向右孩子节点再次进行查找，当key<root->key，从左边的孩子节点进行查找，否则，就证明查找到了。

◆下面是详细的代码（实现的递归和非递归两种方式）

template<classK,classV>classBSTree{typedefBSTNode<K,V>Node;public:BSTree()//构造:_root(NULL){}boolInsert(constK&key,constV&value)//非递归插入{if(_root==NULL)//根节点为空{_root=newNode(key,value);returntrue;}Node*cur=_root;if(cur->_left==NULL&&cur->_right==NULL)//父节点的左右节点为空{if(cur->_key<key){cur->_right=newNode(key,value);}elseif(cur->_key>key){cur->_left=newNode(key,value);}else{returnfalse;}}else{Node*parent=cur;while(cur){parent=cur;if(cur->_key<key){if(parent->_right==NULL)//右节点为空{parent->_right=newNode(key,value);}cur=cur->_right;}elseif(cur->_key>key){if(parent->_left==NULL)//左节点为空{parent->_left=newNode(key,value);}cur=cur->_left;}else//数据在树中已经存在，防止数据冗余{returnfalse;}}}returntrue;}boolRemove(constK&key)//非递归删除{if(_root==NULL)//根节点为空{returnfalse;}if(_root->_left==NULL&&_root->_right==NULL)//根节点的左右节点为空{if(_root->_key==key){delete_root;_root=NULL;returntrue;}else{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;}else//找到要删除的节点{Node*del=cur;if(cur->_left==NULL)//左为空{if(parent==NULL)//cur节点没有父节点{_root=cur->_right;}else//cur有父节点{if(parent->_left==cur){parent->_left=cur->_right;}else{parent->_right=cur->_right;}}}elseif(cur->_right==NULL)//右为空{if(parent==NULL){_root=cur->_left;}else{if(parent->_left==cur){parent->_left=cur->_left;}else{parent->_right=cur->_left;}}}else//左、右为空{//找右树的最左节点//找到的节点与cur交换再删除parent=cur;Node*firstLeft=cur->_right;while(firstLeft->_left){parent=firstLeft;parent=firstLeft->_left;}swap(cur->_key,firstLeft->_key);swap(cur->_value,firstLeft->_value);del=firstLeft;if(parent->_left==firstLeft){parent->_left=firstLeft->_right;}else{parent->_right=firstLeft->_right;}}deletedel;returntrue;}}returnfalse;}Node*Find(constK&key)//非递归查找{if(_root==NULL){returnNULL;}Node*cur=_root;while(cur){if(cur->_key<key){cur=cur->_right;}elseif(cur->_key>key){cur=cur->_left;}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()//递归实现中序遍历{_Inorder(_root);}protected:bool_Insert_R(Node*&root,constK&key,constV&value)//递归实现插入节点{if(root==NULL){root=newNode(key,value);//添加引用会更改_rootreturntrue;}if(root->_key<key){return_Insert_R(root->_right,key,value);}elseif(root->_key>key){return_Insert_R(root->_left,key,value);}else{returnfalse;}}Node*_Find_R(Node*&root,constK&key)//递归实现查找{if(root==NULL){returnNULL;}if(root->_key<key){return_Find_R(root->_right,key);}elseif(root->_key>key){return_Find_R(root->_left,key);}else{returnroot;}}bool_Remove_R(Node*&root,constK&key){if(root==NULL){returnfalse;}if(root->_key>key){return_Remove_R(root->_left,key);}elseif(root->_key<key){return_Remove_R(root->_right,key);}else{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(root->_right,key);deletedel;returntrue;}}returnfalse;}void_Inorder(Node*root)//中序遍历{if(root==NULL){return;}_Inorder(root->_left);cout<<root->_key<<"";_Inorder(root->_right);}protected:Node*_root;};