数据结构与算法-二叉搜索树

1. 基础数据结构

//结点结构
typedef  struct BiTNode
{
    //结点数据
    int data;
    //左右孩子指针
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

2. 树的增删查

2.1 搜索

因为插入前要搜索是否存在，所以先实现搜索。

/// 递归查找二叉排序树T中，是否存在key
/// @param T 二叉排序树
/// @param key 被查询值
/// @param f 指针f指向T的双亲，初始值为NULL
/// @param p 最后一个被访问结点的指针引用
///
/// 若指针p指向查找路径上访问的最后一个结点则返回FALSE
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) {
    if (!T) { // 空树
        *p = f; // 查询失败，指回双亲结点
        return FALSE;
    } else if (key == T->data) { // 根节点查询成功
        *p = T;
        return TRUE;
    } else if (key < T->data) { // 查询值跟小，则在左子树中找
        return SearchBST(T->lchild, key, T, p);
    } else { // 查询值更大，则在右子树中找
        return SearchBST(T->rchild, key, T, p);
    }
    return TRUE;
}

2.1 插入

/// 二叉排序树的插入
/// @param T 二叉排序树
/// @param key 被插入值
Status InsertBST(BiTree *T, int key) {
    BiTree p, tr;
    if (!SearchBST(*T, key, NULL, &p)) { // 没有查询到
        tr = (BiTree)malloc(sizeof(BiTNode));
        tr->data = key;
        tr->lchild = tr->rchild = NULL;
        if (!p) { // 空树时，*p = f = NULL
            *T = tr; // 直接作为根节点
        } else if (key < p->data) { // 如果key<p->data，则插入为左孩子
            p->lchild = tr;
        } else { // 如果key>p->data，则插入为右孩子
            p->rchild = tr;
        }
        return TRUE;
    }
    return FALSE;
}

2.3 删除

/// 删除某个结点
/// @param p 结点指针
Status Delete(BiTree *p) {
    BiTree tmp, tr;
    if (!(*p)->rchild) { // 如果没有右子树
        tmp = *p; // 方便后续删除
        *p = (*p)->lchild; // 左子树补上
        free(tmp); // 释放被删除结点
    } else if (!(*p)->lchild) { // 如果没有左子树
        tmp = *p; // 方便后续删除
        *p = (*p)->rchild; // 右子树补上
        free(tmp); // 释放被删除结点
    } else { // 左右子树都不为空
        // 可以选前序遍历，左边最后一个结点，或右边第一个结点
        // 下面以左边为例，左边镜像改一下差不多的
        tmp = *p; // 双亲节点
        tr = tmp->lchild; // 左子树
        while (tr->rchild) { // 找到最后一个右子树(前序遍历的最后一个结点)，该结点没有右儿子
            tmp = tr;
            tr = tr->rchild;
        }
        (*p)->data = tr->data; // 交换被删除结点和最后一个结点的值(后面直接删除tr结点就好了)
        // 删除之前需要把被删除结点tr的子树连接上
        // tr是最后一个右子树，该结点没有右儿子，所以用左孩子
        if (tmp == *p) { // 双亲节点没有发生变化，说明没有右子树
            tmp->lchild = tr->lchild;
        } else {
            tmp->rchild = tr->lchild;
        }
        free(tr); // 释放多余节点
    }
    return TRUE;
}

/// 递归查找要删除的结点
/// @param T 二叉排序树
/// @param key 被删除值
Status DeleteBST(BiTree *T, int key) {
    if (!*T) { // 空树，删除失败
        return FALSE;
    } else {
        if (key == (*T)->data) { // 找到目标结点开始删除
            return Delete(T);
        } else if (key < (*T)->data) { // 被删除值更小，从左子树里面找
            return DeleteBST(&(*T)->lchild, key);
        } else { // 被删除值更大，从右子树里面找
            return DeleteBST(&(*T)->rchild, key);
        }
    }
}