【数据结构】二叉排序树（查找+插入+删除+效率分析）完整代码+解析

【数据结构】二叉排序树（查找+插入+删除+效率分析）完整代码+解析

引用

CSDN

1.

https://blog.csdn.net/m0_61628700/article/details/138794131

二叉排序树（Binary Search Tree，BST）是一种重要的数据结构，它能够高效地支持查找、插入和删除操作。本文将详细介绍二叉排序树的基本概念、操作方法及其效率分析，并提供完整的代码实现。

3.1 二叉排序树

3.1.1 定义

二叉排序树又称二叉查找树（BST，Binary Search Tree），是一种具有以下性质的二叉树：

• 左子树结点值 < 根结点值 < 右子树结点值

进行中序遍历，可以得到一个递增的有序序列。

3.1.2 查找操作

步骤：

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

代码实现：

//二叉排序树结点
typedef struct BSTree{
    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; //key小，则在左子树上找
        else
            T=T->rchild; //key大，则在右子树上找
    }
    return T;
}

递归实现：

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)，非递归是O(1)，所以非递归效率更加好。

3.1.3 插入操作

思路：

• 若原二叉树为空，则直接插入结点；
• 否则，若关键字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;
    }
    else if(k==T->key) //树中存在相同关键字的结点，插入失败
        return 0;
    else if(k<T->key) //插入到T的左子树
        return BST_Insert(T->lchild,k);
    else //插入到T的右子树
        return BST_Insert(T->rchild,k);
}

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

二叉排序树的构造：

//按str[]中的关键字序列建立二叉树
void Creat_BST(BSTree &T,int str[],int n){
    T=NULL;
    int i=0;
    //依次将每个关键字插入到二叉排序树中
    while(i<n){
        BST_Insert(T,str[i]);
        i++;
    }
}

注：不同的关键字序列可能得到同款二叉排序树，也可能不同。

3.1.4 删除操作

步骤：

1. 先搜索找到目标结点：

• 若被删结点z是叶子结点，则直接删除，不会破坏二叉排序树的性质。
• 若结点z只有一棵左子树或右子树，则让z的子树成为z的子树成为z父节点的子树，代替z的位置。
• 若z既有左子树又有右子树：
• 方法一：则令z的直接后继（中序遍历z子树后的第一个结点）代替z，然后从二叉排序树中删去这个直接后继。
• z的后继：z的右子树中最左下结点（该结点一定没有左子树）。
• 方法二：用直接前驱替换直接后继，其他方法不变。
• z的前驱：z的左子树中最右下结点（该结点一定没有右子树）。

3.1.5 效率分析

查找长度：

在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度。

时间复杂度：

最差情况下O(h)，即为树高

完整代码实现

#include <iostream>
using namespace std;
//二叉排序树结点
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
// 在二叉排序树中搜索关键字为key的结点
BSTNode* BSTSearch(BSTree T, int key) {
    if (T == NULL || T->key == key)
        return T;
    if (key < T->key)
        return BSTSearch(T->lchild, key);
    else
        return BSTSearch(T->rchild, key);
}
// 在二叉排序树中查找最小值结点
BSTNode* findMin(BSTree T) {
    if (T == NULL)
        return NULL;
    else if (T->lchild == NULL)
        return T;
    else
        return findMin(T->lchild);
}
// 删除结点z
void BST_Delete(BSTree &T, int key) {
    if (T == NULL)
        return;
    else if (key < T->key)
        BST_Delete(T->lchild, key);
    else if (key > T->key)
        BST_Delete(T->rchild, key);
    else {
        // 找到了要删除的结点
        if (T->lchild && T->rchild) {
            // 如果有两个子节点
            BSTNode* minRight = findMin(T->rchild); // 找到右子树的最小值结点
            T->key = minRight->key; // 用右子树的最小值替换当前结点
            BST_Delete(T->rchild, minRight->key); // 删除右子树的最小值结点
        } else {
            // 如果只有一个子节点或者是叶子结点
            BSTNode* temp = T;
            if (T->lchild == NULL) // 如果只有右子树或者是叶子结点
                T = T->rchild;
            else if (T->rchild == NULL) // 如果只有左子树
                T = T->lchild;
            free(temp); // 释放删除结点的内存
        }
    }
}
//在二叉排序树插入关键字为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;
    }
    else if(k==T->key) //树中存在相同关键字的结点，插入失败
        return 0;
    else if(k<T->key) //插入到T的左子树
        return BST_Insert(T->lchild,k);
    else //插入到T的右子树
        return BST_Insert(T->rchild,k);
}
//按str[]中的关键字序列建立二叉树
void Creat_BST(BSTree &T,int str[],int n){
    T=NULL;
    int i=0;
    //依次将每个关键字插入到二叉排序树中
    while(i<n){
        BST_Insert(T,str[i]);
        i++;
    }
}
// 中序遍历打印二叉排序树
void InOrder(BSTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        cout << T->key << " ";
        InOrder(T->rchild);
    }
}
int main() {
    BSTree T = NULL;
    // 插入操作测试
    int arr[] = {50, 30, 70, 20, 40, 60, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    Creat_BST(T, arr, n);
    cout << "Binary Search Tree (Inorder): ";
    InOrder(T);
    cout << endl;
    // 搜索操作测试
    int searchKey = 40;
    BSTNode* searchResult = BSTSearch(T, searchKey);
    if (searchResult != NULL)
        cout << "Key " << searchKey << " found in the tree." << endl;
    else
        cout << "Key " << searchKey << " not found in the tree." << endl;
    // 删除操作测试
    int deleteKey = 30;
    cout << "Deleting key " << deleteKey << endl;
    BST_Delete(T, deleteKey);
    cout << "Binary Search Tree after deletion: ";
    InOrder(T);
    cout << endl;
    return 0;
}