二叉排序树（BST）

1 二叉排序树定义：

二叉排序树(Binary Sort Tree)或者是一棵空树;或者是具有下列性质的二叉树:
(1) 若左子树不空，则左子树上所有结点的值均小于根结点的值;若右子树不空，则右
子树上所有结点的值均大于根结点的值。
(2) 左右子树也都是二叉排序树。

一棵二叉树是二叉排序树的(必要但不充分)条件是树中任一结点的关键字值都大于左子女的关键字值，小于右子女的关键字值。
一棵二叉树是二叉排序树是树中任一结点的关键字值都大于左子女的关键字值，小于右子女的关键字值的（充分但不必要)条件。

若按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列。
通常，取二叉链表作为二叉排序树的存储结构。
结点类型定义如下:

typedef struct Node {
    KeyType key;//关键字域
    //其它数据域
    struct Node *lChild, *rChild;
} BSTNode;

2 二叉排序树的查找过程

从其定义可见，二叉排序树的查找过程是一个递归过程，具体为:
① 若查找树为空，查找失败。
②查找树非空，将给定值 key 与查找树的根结点关键码比较。
③若相等，查找成功，结束查找过程，否则，
a.当给 key 小于根结点关键码，查找将在以左孩子为根的子树上继续进行，转①
b.当给 key 大于根结点关键码，查找将在以右孩子为根的子树上继续进行，转①

(1)递归算法

BSTNode *BST_Search(BSTNode *T, KeyType key) {
    if (T == NULL) {
        return (NULL);
    } else {
        if (T->key == key) {
            return (T);
        } else if (key < T->key) {
            return (BST_Search(T->lChild, key));
        } else {
            return (BST_Search(T->rChild, key));
        }
    }
}

(2) 非递归算法

BSTNode *BST_Serach(BSTNode *T, KeyType key) {
    BSTNode *p = T;
    while (p != NULL && p->key != key) {
        if (key < p->key) {
            p = p->lChild;
        } else {
            p = p->rChild;
        }
    }
    if (p->key == key) {
        return (p);
    } else {
        return (NULL);
    }
}

3 BST树的插入

(1)递归算法

void insertBST(BSTNode * T,KeyType key) {
    BSTNode *p = (BSTNode *) malloc(sizeof(BSTNode));
    p->key = key;
    p->lChild = p->rChild = NULL;
    if (T == NULL) {
        T = p;
    } else {
        if(T->key == p->key) {
            return;
        } else if (p->key < T->key) {
            insertBST(T->lChild, key);
        } else {
            insertBST(T->rChild, key);
        }
    }
}

(2)非递归算法

void insertBST2(BSTNode *T, KeyType key) {
    BSTNode *p = (BSTNode *) malloc(sizeof(BSTNode));//p为新插入的结点
    p->key = key;
    p->lChild = p->rChild = NULL;
    BSTNode *q = T, *r;//q为遍历的指针。r记录q的父结点，也为最终p结点的父结点。
    if (T == NULL) {
        T = p;
    } else {
        while (q != NULL) {//寻找最终插入的位置，即插入到r结点上
            if (q->key == p->key) {//如果已存在，不插入
                return;
            }
            r = q;//r作为q的父结点
            if (p->key < q->key) {
                q = q->lChild;
            } else {
                q = q->rChild;
            }
        }
        if (p->key < r->key) {
            r->lChild = p;
        } else {
            r->rChild = p;
        }
    }
}

4 二叉排序树删除

从 BST 树上删除一个结点，仍然要保证删除后满足 BST 的性质。设被删除结点为 p，其父结点为 f ，删除情况如下:
①若 p 是叶子结点: 直接删除 p。
②若 p 只有一棵子树(左子树或右子树):直接用 p 的左子树(或右子树)取代 p 的位置而成为f的一棵子树。
③若 p 既有左子树又有右子树 :有两种方法
a.用 p 的直接前驱结点代替 p。
b.用 p 的直接后继结点代替 p。
代码如下：

void deleteBST(BSTNode *T, KeyType key) {
    BSTNode *p = T, *f = NULL, *q, *s;
    while (p != NULL && p->key != key) {//找到要删除的结点p，用f记录p的父结点
        f = p;
        if (key < p->key) {
            p = p->lChild;//搜索左子树
        } else {
            p = p->rChild;//搜索右子树
        }
    }
    if (p == NULL) {
        return;//没有要删除的结点
    }
    s = p;//最终删除s
    if (p->lChild != NULL && p->rChild != NULL) {//如果p既有左子树又有右子树，用p的直接前驱代替p
        f = p;
        s = p->lChild;//p的直接前驱为p的左子树的最右边的结点
        while (s->rChild != NULL) {//
            f = s;
            s = s->rChild;
        }
        p->key = s->key; //用s代替p之后，此时需要删除s，s可能有左子树，右子树一定为空
    }
    if (s->lChild != NULL) {//如果p是叶子结点,q为NULL；如果p只有一棵子树，s可能有左子树可能有右子树；如果p有两棵子树，则s一定只有左子树
        q = s->lChild;
    } else {
        q = s->rChild;
    }
    if (f == NULL) {
        T = q;
    } else if (f->lChild == s) {//f是s的父结点，s是q的父结点
        f->lChild = q;//如果s是f的左子树，删除s的时候，把q挂在f的左边
    } else {
        f->rChild = q;
    }
    free(s);
}

测试代码：

int main() {
    BSTNode *A = (BSTNode *) malloc(sizeof(BSTNode));
    BSTNode *B = (BSTNode *) malloc(sizeof(BSTNode));
    BSTNode *C = (BSTNode *) malloc(sizeof(BSTNode));
    BSTNode *D = (BSTNode *) malloc(sizeof(BSTNode));
    BSTNode *E = (BSTNode *) malloc(sizeof(BSTNode));
    BSTNode *F = (BSTNode *) malloc(sizeof(BSTNode));
    A->key = 10;
    A->lChild = B;
    A->rChild = D;
    B->key = 5;
    B->lChild = NULL;
    B->rChild = C;
    C->key = 8;
    C->lChild = F;
    C->rChild = NULL;
    D->key = 15;
    D->lChild = E;
    D->rChild = NULL;
    E->key = 13;
    E->lChild = E->rChild = NULL;
    F->key = 7;
    F->lChild = F->rChild = NULL;
    deleteBST(A, 10);
    return 0;
}

二叉排序树（BST）