二叉查找树（binary search tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均不小于它的根结点的值； 它的左、右子树也分别为二叉排序树。
二叉排序树的查找过程和二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高o(log(n)).
特性：1.从根节点一直往左走，知道无左路可走，即得到最小元素；从根节点一直往右左，直到无右路可走，即得到最大元素。
2.一个节点的后继节点，必定无左子树，有或者没有右子树；一个节点的前驱节点，必定无右子树，有或者没有左子树。
二叉查找树的插入过程如下：1.若当前的二叉查找树为空，则插入的元素为根节点，2.若插入的元素值小于根节点值，则将元素插入到左子树中，3.若插入的元素值不小于根节点值，则将元素插入到右子树中。
在二叉排序树b中查找x的过程为：若b是空树，则搜索失败若x等于b的根结点的数据域之值，则查找成功若x小于b的根结点的数据域之值，则查找左子树；否则，查找右子树。
将一个结点从二叉查找树中删除之后，剩下的结点可能会不满足二叉查找树的性质，因此，在删除结点之后要对树进行调整，使其满足二叉查找树的性质。根据结点的孩子的数量，将删除操作分为三种情况，我们记要删除的结点为z，实际上删除的结点为y。
1. z结点没有孩子。
如下图a所示，我们要删除值为13的结点，因为结点没有孩子，所以删除之后不会影响到二叉树的整体性质，也
就是说，直接将13这个结点删除即可，如图a所示，从左边的二叉树删除13这个点之后变到右边的二叉树。
2. z结点有一个孩子。
如下图b所示，要删除的值为16的结点有一个孩子，而且是右孩子，那么从图上来看，如果，我们将16去掉，然后把以20为结点的子树作为15的右子树，那么整棵树还是符合二叉查找树的性质的，因此，有一个孩子的结点的删除操作，就是要将其孩子作为其父结点的孩子即可。如图b所示。
3. z结点有两个孩子。
如下图c所示，要删除的值为5的结点，有两个孩子，删除之后肯定整棵树就不符合二叉查找树的性质了，因此要
进行调整，我们发现，将5的后继，值为6的结点来放到5的位置，然后将6的孩子7作为6的父结点10的孩子，如下图c
所示，我们要删除的是z结点，而我们实际要删除y结点，并替换z结点。这里需要注意的一点是，如果一个结点有右
孩子，则该结点的后继，至多有一个子女，而且是右孩子。因为假如该结点的后继有左孩子和右孩子，那么其左孩子
的值肯定是介于该结点和其后继之间的，那么按照二叉查找树的性质，这个左孩子就应该是该结点的后继，所以，这
与原先的后继相互矛盾，因此，结论成立。
程序代码如下： searchbitree.h文件内容
#ifndef searchbitree_h
#define searchbitree_h
#include
//定义二叉树结点结构
typedef struct binode{
int data;
struct binode *lchild;
struct binode *rchild;
binode(int value):data(value),lchild(null),rchild(null){}
}*bitree;
//二叉查找树查找算法,如果不存在则返回false,存在则返回ture
bool searchvalue(bitree root,int value){
while(root!=null){
if(root->data==value)
return true;
else if(root->data>value)
root=root->lchild;
else root=root->rchild;
}
return false;
}
//二叉查找树插入算法（建立二叉树算法）
void insertsearchtree(bitree &root,int value){
//如果为空树，则插入
if(root==null){
root=new binode(value);
}else{
//根节点值大于插入值，则插入左子树
if(root->data>value)
insertsearchtree(root->lchild,value);
else
//插入右子树
insertsearchtree(root->rchild,value);
}
}
//中序遍历二叉查找树，得到的是一个有序序列
void inordertraverse(bitree root){
if(root!=null){
inordertraverse(root->lchild);
std::cout<data<<" ";
inordertraverse(root->rchild);
}
}
//获得二叉查找树最大值,如果为空树，则返回-1
int findmax(bitree root){
if(root==null)
return -1;
while(root->rchild!=null){
root=root->rchild;
}
return root->data;
}
//获得二叉查找树最小值,如果为空树，则返回-1
int findmin(bitree root){
if(root==null)
return -1;
while(root->lchild!=null){
root=root->lchild;
}
return root->data;
}
//得到待删除结点的父节点和本身结点指针
void findpostion(bitree root, int deletevalue, bitree& deletenode,bitree& parentnode){
deletenode=root;
while(deletenode!=null){
if(deletenode->data==deletevalue){
return;
}else if(deletenode->data>deletevalue){
parentnode=deletenode;
deletenode=deletenode->lchild;
}else{
parentnode=deletenode;
deletenode=deletenode->rchild;
}
}
}
//二叉查找树删除算法
void deletesearchtree(bitree &root,int deletevalue){
bitree deletenode=null,parentnode=null;
//得到待删除结点的指针和指向父节点的指针
findpostion(root,deletevalue,deletenode,parentnode);
//std::cout<data<<" "<data<lchild==null && deletenode->rchild==null){
if(deletenode=parentnode->lchild)
parentnode->lchild=null;
else if(deletenode=parentnode->rchild)
parentnode->rchild=null;
else
//删除的是根节点
parentnode=null;
delete deletenode;
}else if(deletenode->lchild==null && deletenode->rchild!=null){ //待删除结点只有右子树
if(root->data==deletenode->data)//删除的是根节点
root=deletenode->rchild;
else{
if(deletenode==parentnode->lchild)
parentnode->lchild=deletenode->rchild;
else
parentnode->rchild=deletenode->rchild;
}
delete deletenode;
}else if(deletenode->lchild!=null && deletenode->rchild==null){ //待删除结点只有左子树
if(root->data==deletenode->data)//删除的是根节点
root=deletenode->rchild;
else{
if(deletenode==parentnode->lchild)
parentnode->lchild=deletenode->lchild;
else
parentnode->rchild=deletenode->lchild;
}
delete deletenode;
}else{ //待删除结点既有左子树又有右子树
bitree temp = deletenode->lchild;
bitree tempparent = deletenode;
//找到待删除结点的直接前驱
while(temp->rchild != null){
tempparent = temp;
temp = temp->rchild;
}
//交换待删除结点和其前驱结点的值
deletenode->data = temp->data;
//此处有两种情况需要考虑，具体自己画图分析
if(tempparent->lchild == temp){
tempparent->lchild = temp->lchild;
}else{
tempparent->rchild = temp->lchild;
}
delete temp;
}
}
#endif main.cpp文件内容
#include
#include "searchbitree.h"
using namespace std;
int main(){
bitree root=null;
int value[]={15,5,16,3,12,20,10,13,18,23,6,7};
//插入建立二叉查找树
for(int i=0;i<12;i ){
insertsearchtree(root,value[i]);
}
//中序遍历二叉查找树，得到有序序列
cout<<"中序遍历二叉查找树: ";
inordertraverse(root);
cout<
程序运行截图