(38)王道数据结构-二叉排序树

基本概念

二叉排序树，又称二叉查找树，一棵二叉树或者是空二叉树，或者是具有如下特质的二叉树

1.左子树上所以的结点的关键字均小于根结点的关键字
2.右子树上所有结点的关键字均大于根结点的关键字
3.左子树和右子树又各是一棵二叉排序树

左子树结点值 < 根结点值 < 右子树结点值
进行中序遍历，可以得到一个递增的有序序列

二叉排序树可用于元素的有序组织、搜索

查找操作

1.若树非空，目标值与根结点的值比较
2.若相等，则查找成功
3.若小于根结点，则在左子树上查找，否则在右子树上查找
4.查找成功，返回结点指针，查找失败返回NULL

相关代码

//二叉排序树结点
typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

//在二叉树中查找值为key的结点
BSTNode *BST_Search(BSTree T, int key) {
    while (T != NULL && key != T->key) {    //若树空或等于根结点值，则结束循环
        if (key < T->key) { //小于，则在左子树上查找
            T = T->lchild;
        } else {    //大于，则在右子树上查找
            T = T->rchild;
        }
    }
    return T;
}

最坏时间复杂度: O(1)

递归实现

//二叉排序树结点
typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

//在二叉树中查找值为key的结点(递归实现)
BSTNode *BSTSearch(BSTree T, int key) {
    if (T == NULL) {
        return NULL;    //查找失败
    }
    if (key == T->key) {
        return T:       //查找成功
    } else if (key < T->key) {
        return BSTSearch(T->lchild, key);   //在左子树中招
    } else {
        return BSTSearch(T->rchild, key);   //在右子树中找
    }
}

最坏空间复杂度: O(h)

效率分析

在查找运算中，需要对比关键字的次数称为查找长度，反应了查找操作的时间复杂度。若树高h，找到最下层的一个结点需要对比h次

最好情况:
n个结点的二叉树最小高度为[log2n + 1]，平均查找长度=O(long2n)

最坏情况:
每个结点只有一个分支，树高h=结点数n。平均查找长度=O(n)

平均查找长度
英文缩写ASL，值为单层结点树乘以层序号(1,2,3,…)在把每层的值加起来除以结点数

graph TD;
    A(("50"));
    B(("26"));
    C(("66"));
    D(("21"));
    E(("30"));
    F(("60"));
    G(("70"));
    H(("68"));
    
    A-->B;
    A-->C;

    B-->D;
    B-->E;
    C-->F;
    C-->G;

    G-->H;
    G-->N(( ));
    
    style N fill:#f100,stroke-width:0px
    linkStyle 7 stroke:#0ff,stroke-width:0px

查找成功ASL = (1x1 + 2x2 + 3x4 + 4x1)/8 = 2.625

graph TD;
    A(("50"));
    B(("26"));
    C(("66"));
    D(("21"));
    E(("30"));
    F(("60"));
    G(("70"));
    H(("68"));
    
    A-->B;
    A-->C;

    B-->D;
    B-->E;
    C-->F;
    C-->G;

    D-.-R1[ ];
    D-.-R2[ ];
    E-.-R3[ ];
    E-.-R4[ ];
    F-.-R5[ ];
    F-.-R6[ ];
    G-->H;
    G-.-R7[ ];

    H-.-R8[ ];
    H-.-R9[ ];

倒数第二层需要对比3次，共有7个结点
倒数第一层需要对比4次，共有2个结点

查找失败ASL = (3x7 + 4x2)/9 = 3.22

插入操作

若原二叉排序树为空，则直接插入结点。否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树

相关代码

//在二叉排序树插入关键字为k的新结点(递归实现)
int BST_Insert(BSTree &T, int k) {
    if (T == NULL) {    //原树为空，新插入的结点为根结点
        T = (BSTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;   //返回1，插入成功
    } else if (k == T->key) {   //树中存在相同关键字的结点，插入失败
        return 0;
    } else if (k < T->key) {    //插入到左子树
        return BST_Insert(T->lchild, k);
    } else {    //插入到T的右子树
        return BST_Insert(T->rchild, k);
    }
}

最坏空间复杂度:O(h)

构造操作

根据相关数组序列，构造二叉排序树

void Creat_BST(BSTree &T, int str[], int n) {
    T = NULL;   //初始化时T为空树
    int i = 0;
    while (i < n) { //依次将每个关键字插入到二叉排序树中
        BST_Insert(T, str[i]);
        i++;
    }
}

不同的关键字序列可能得到同款二叉排序树
str1 = {50, 66, 26, 21, 30, 70, 68}
str2 = {50, 26, 21, 30, 66, 70, 68}

删除操作

先搜索找到目标结点
1.若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质
2.若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置
3.若结点z有左、右两棵子树，则令z的直接后继(或直接前驱)替代z，然后从二叉排序树中删去这个直接后继(或直接前驱)，这样就转换成了第一种或第二种情况

完整代码

#include<stdio.h>
#include<stdlib.h>
typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

//在二叉树中查找值为key的结点
BSTNode *BST_Search(BSTree T, int key) {
    while (T != NULL && key != T->key) {    //若树空或等于根结点值，则结束循环
        if (key < T->key) { //小于，则在左子树上查找
            T = T->lchild;
        } else {    //大于，则在右子树上查找
            T = T->rchild;
        }
    }
    return T;
}

int BST_Insert(BSTree &T, int k) {
    if (T == NULL) {    //原树为空，新插入的结点为根结点
        T = (BSTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;   //返回1，插入成功
    } else if (k == T->key) {   //树中存在相同关键字的结点，插入失败
        return 0;
    } else if (k < T->key) {    //插入到左子树
        return BST_Insert(T->lchild, k);
    } else {    //插入到T的右子树
        return BST_Insert(T->rchild, k);
    }
}

void Creat_BST(BSTree &T, int str[], int n) {
    T = NULL;   //初始化时T为空树
    int i = 0;
    while (i < n) { //依次将每个关键字插入到二叉排序树中
        BST_Insert(T, str[i]);
        i++;
    }
}

void visit(BSTree root) {
    printf("%d ", root->key);
}

//中序遍历
void midOrder(BSTree T) {
    if (T != NULL) {
        midOrder(T->lchild);    //递归遍历左子树
        visit(T);   //访问根节点
        midOrder(T->rchild);    //递归遍历右子树
    }
}

//删除函数
void DeleteBST(BSTNode* T, int key) {
    //初始化
    BSTNode* p = T;
    BSTNode* f = NULL;
    BSTNode* q = NULL;
    //循环找p->key==key的值，以及它的双亲结点
    while (p) {
	    if (key == p->key) {
	         break;
	    }
	    f = p;//f为p的双亲结点
	    if (key < p->key) { //在左子树找
	        p = p->lchild;
	    } else {  //在右子树找
	        p = p->rchild;
	    }
    }
    //如果没找到
    if (!p) {
        return;
    }
    //考虑三种情况：左右都不为空、左子树不为空、右子树不为空
    q = p;
    //1.左右都不为空
    if ((p->lchild) && (p->rchild)) {
	    BSTNode* s = p->lchild;
	    q = p;
	    //找到左子树的最右结点，即其直接前驱
	    while (s->rchild) {
            q = s;
            s = s->rchild;
	    }
	    p->key = s->key;//令*p的直接前驱代替*p，即s代替p
	    if (q != p) {
	        q->rchild = s->lchild;//重接*q的右子树
	    } else {
	        q->lchild = s->lchild;//重接*q的左子树
	    }
        delete(s);
	    return;
    } else if (p->lchild) { //2.没有右子树
	    //置换
	    q = p;//q指向要删除的结点
	    p = p->lchild;//p指向它的左孩子
    } else if (p->rchild) {   //3.没有左子树
	    //置换
	    q = p;//q指向要删除的结点
	    p = p->rchild;//p指向它的右孩子
    } else if (!p->lchild && !p->rchild) { //4.是叶子结点
        //置换
	    q = p;
	    p = NULL;
    }
    //开始重接删除结点的左孩子或右孩子
    if (!f) {
        T = p;//删除的是根节点
    } else if (q == f->lchild) {
        f->lchild = p;
    } else if (q == f->rchild) {
        f->rchild = p;
    }
    delete(q);
}

int main(void) {
    int str1[] = {50, 66, 26, 21, 30, 70, 68};
    BSTree T;
    BSTNode *node;
    int n = sizeof(str1) / 4;
    Creat_BST(T, str1, n);
    
    //查找验证
    node = BST_Search(T, 66);
    printf("node key is=%d\n", node->key);
    
    //中序遍历
    midOrder(T);
    
    printf("\n");
    //删除验证
    DeleteBST(T, 68);
    midOrder(T);
    
    return 0;
}