二叉搜索树（Binary Search Tree）

什么是二叉查找树

二叉搜索树，以下简称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 in time 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;
}