二叉查找树定义

二叉查找树（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 <iostream>

//定义二叉树结点结构
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<<root->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<<parentNode->data<<" "<<deleteNode->data<<std::endl;
	//待删除结点是叶子结点（特殊情况只有一个根节点，需要特殊处理）
	if(deleteNode->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<iostream>
#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<<endl;
	//获得二叉查找树最大值
	cout<<"二叉查找树最大值: "<<FindMax(root)<<endl;
	//获得二叉查找树最小值
	cout<<"二叉查找树最大值: "<<FindMin(root)<<endl;
	//二叉查找树查找算法
	cout<<"查找11: "<<boolalpha<<SearchValue(root,11)<<endl;
	cout<<"查找12: "<<SearchValue(root,12)<<endl;
	//二叉查找树删除算法
	cout<<"删除结点12后输出: ";
	DeleteSearchTree(root,12);
	InorderTraverse(root);
	return 0;
}

程序运行截图