什么是二叉查找树
二叉搜索树，以下简称BST。他有如下特性:
- 它是一个二叉树。
- 如果x是BST的一个节点，L为x的左子树中的任意一个节点，R为x的右子树中的任意一个节点，满足
搜索树支持很多动态集操作（dynamic-set），比如SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR,INSERT, 和DELETE 因此，我们可以将搜索树用作字典和优先级队列
BST
如果中序遍历BST将会得到一个有序的序列。这个是显然的，二叉树的性质就是左边元素小，右边元素大，按左中右的顺序遍历得到的就是有序的。
BST
BST查询相关的操作
①元素查找
在BST中查找关键字为k的节点，查找成功返回指向该节点的指针，失败返回NULL;
②最大值和最小值
最大值在最右边
最小值在最左边
③前驱和后继
节点x的前驱是指比他小的最大一个节点
节点x的后继是指比他大的最小一个节点
求节点的前驱和后继节点是对称的，前驱和后继节点可能不存在，比如一个BST中最大值没有后继，最小值没有前驱。下面以求后继为例，求后继节点分为两种情况：
-
case1: 有右孩子，这种情况比较简单s，直接转化为以右孩子为根节点的子树的最小值。即y节点。
存在右孩子 -
case2:没有右孩子，需要向上查找第一个左拐的祖先
没有右孩子
We can implement the dynamic-set operations SEARCH, MINIMUM, MAXIMUM,
SUCCESSOR, and PREDECESSOR so that each one runs intime on a binary
search tree of height h
④插入
插入和查找类似，需要一个尾指针记录插入的位置
⑤删除
删除操作分为三种情况
1.要删除的节点没有左右孩子。直接删除
2.要删除的节点只有左孩子或只有右孩子。例如要删除z,只需要将z的parent q和l链接起来就行。
只有一个孩子
3.要删除的节点既有左孩子也有右孩子 。删除思想是使用后继替换删除的节点转化为第二种情况。根据删除节点的后继是否为删除节点的右孩子，又可以分为两种情况：
3.1 删除节点的后继为右孩子：
后继为右孩子
3.2 删除节点的后继不是右孩子：
后继不是右孩子
c语言实现
BST.h
#ifndef BST_H
#define BST_H
#endif
#include<stdio.h>
#include<stdlib.h>
typedef int BSTELEM_TYPE;
//typedef enum{false,true } bool;//定义bool
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
typedef struct BSTNode{
struct BSTNode *left;
struct BSTNode *right;
struct BSTNode *parent;
BSTELEM_TYPE key;
}BSTNode,*BSTTree;
//递归查找
//根据指针x所指的BST中递归的查找关键字等于k 的元素
//若查找成功返回指向该数据元素节点的指针，失败返回null;
BSTTree Tree_Search(BSTTree x,BSTELEM_TYPE k);
//迭代查找
BSTTree Iterative_Tree_Search(BSTTree x,BSTELEM_TYPE k);
//查找x指针指向的BST的最小值
BSTTree Tree_Minimum(BSTTree x);
//查找x指针指向的BST的最大值
BSTTree Tree_Maximum(BSTTree x);
//查找x指针指向的BST的后继
BSTTree Tree_Successor(BSTTree x);
BSTTree Tree_Predecessor(BSTTree x);
int Tree_Insert(BSTTree *t,BSTELEM_TYPE k);
//递归实现中序遍历
void inOrderTraverse(BSTTree t);
void Transplant(BSTTree *x,BSTTree *y);
void Tree_Delete(BSTTree *t, BSTELEM_TYPE k) ;
BST.c
#ifndef BST_C
#define BST_C
#endif
#include "BST.h"
BSTTree Tree_Search(BSTTree x,BSTELEM_TYPE k){
//x为空或者x指向的元素等于k，查找结束
if((x==NULL)||EQ(k,x->key)){
return x;
//k 小于x指向的元素，在左子树中查找
}else if(LT(k,x->key)) {
return Tree_Search(x->left,k);
//k 大于x指向的元素，在右子树中查找
}else {
return Tree_Search(x->right,k);
}
}
BSTTree Iterative_Tree_Search(BSTTree x,BSTELEM_TYPE k){
while(x&&!EQ(k,x->key)){
if(LT(k,x->key)){
x=x->left;
}else{
x=x->right;
}
}
return x;
}
BSTTree Tree_Minimum(BSTTree x){
if(!x){
return NULL;
}
while(!x->left){
x=x->left;
}
return x;
}
BSTTree Tree_Maximum(BSTTree x){
if(!x){
return NULL;
}
while(!x->right){
x=x->right;
}
return x;
}
BSTTree Tree_Successor(BSTTree x){
//case 1 有右孩子 ,直接返回右孩子的最小值
if(x->right!=NULL){
return Tree_Minimum(x->right);
}
//case 2 没有右孩子，找到第一个左拐的祖先
BSTTree y=x->parent;
while(y!=NULL&&y->right==x){//右拐的都是比他小的，继续循环
x=y;
y=y->parent;
}
return y;
}
BSTTree Tree_Predecessor(BSTTree x){
//case1 有左孩子，直接返回左孩子的最大值
if(x->left!=NULL){
return Tree_Maximum(x->left);
}
BSTTree y=x->parent;
while(y!=NULL&&y->left==x){//左拐的都是比他大的，继续向上
x=y;
y=y->parent;
}
return y;
}
int Tree_Insert(BSTTree *t,BSTELEM_TYPE k){
//重复元素不插入
if(Iterative_Tree_Search(*t,k)){
return 0;
}
//z为待插入元素，为期动态分配空间同时初始化
BSTTree z=(BSTTree)malloc(sizeof(BSTNode));
z->key=k;
z->left=z->right=z->parent=NULL;
//树为空直接插入
if(*t==NULL){
*t=z;
return 1;
}
BSTTree y;//记录待插入节点z的父亲指针,尾指针
BSTTree x=*t;
while(x!=NULL){
y=x;
if(LT(k,x->key)){
x=x->left;
}else{
x=x->right;
}
}
//y即为z的父指针
z->parent=y;
if(LT(k,y->key)){
y->left=z;
}else{
y->right=z;
}
return 1;
}
void inOrderTraverse(BSTTree t){
if(t){
inOrderTraverse(t->left);
printf("%d",t->key);
inOrderTraverse(t->right);
}
}
//将x的父节点和y连起来
void Transplant(BSTTree *x,BSTTree *y){
if((*x)->parent==NULL){
return;
}else if((*x)->parent->left==*x){
(*x)->parent->left=*y;
}else{
(*x)->parent->right=*y;
}
if(*y!=NULL){
(*y)->parent=(*x)->parent;
}
}
void Tree_Delete(BSTTree *t, BSTELEM_TYPE k) {
BSTTree z=Iterative_Tree_Search(*t,k);
//要删除的节点不存在，直接返回
if(z==NULL){
return ;
}
//左孩子不存在
if(z->left==NULL){
Transplant(&z,&z->right);
//右孩子不存在
}else if(z->right==NULL){
Transplant(&z,&z->left);
}else {
BSTTree y= Tree_Successor(z);
if(y->parent!=z){//后继不是右孩子
Transplant(&y,&y->right);
y->right=z->right;
y->right->parent=y;
}
Transplant(&z,&y) ;
y->left=z->left;
y->left->parent=y;
}
z->left=z->right=z->parent=NULL;
free(z);
}
void createBST(BSTTree *t,int a[],int n){
int i=0;
for(i;i<n;i++){
Tree_Insert(t,a[i]);
}
}
int main(){
BSTTree t=NULL;
int a[]={10,5,15,18,17,16};
//创建BST
createBST(&t,a,sizeof(a)/sizeof(int));
//删除key为15的节点
Tree_Delete(&t,15);
中序遍历
inOrderTraverse(t);
return 0;
}
