数据结构与算法: 二叉搜索树 C语言描述

作者: 稀土掘金  更新时间:2021-01-15 18:15:16  原文链接


1. 目标:实现一个简易二叉搜索树

期望构建一个这样的简易二叉搜索树:

  • 节点是int,不区分 keyvalue
  • 不允许相同数值的插入
  • 假设每次 malloc 都能成功申请到内存

2. 构建二叉搜索树

2.1 二叉树节点结构体

typedef struct BSTreeNode {
    int    data; //数据域
    struct BSTreeNode *left; //左子结点
    struct BSTreeNode *right; //右子结点
} BSTreeNode;

2.2 插入节点 方法一

//1.第一种,传入指针,返回根节点
BSTreeNode *insert(BSTreeNode *root, int data)
{
    if (NULL == root)
    {
        struct BSTreeNode *node;
        node        = (struct BSTreeNode *)malloc(sizeof(struct BSTreeNode));
        node->data  = data;
        node->right = NULL;
        node->left  = NULL;
        return node;
    }

    if (data > root->data)
    {
        root->right = insert(root->right, data);
    }else{
        root->left  = insert(root->left, data);
    }
    return root;
}

2.3 插入节点 方法二

//2.第二种 传入二级指针,即指针的指针,无需返回
void insert(BSTreeNode **root, int data)
{
    if (NULL == *root)
    {
        *root = (struct BSTreeNode *)malloc(sizeof(struct BSTreeNode));
        (*root)->data = data;
        (*root)->left = NULL;
        (*root)->right = NULL;
    }else{
        if (data > (*root)->data)
        {
            insert(&(*root)->right, data);
        }else{
            insert(&(*root)->left, data);
        }
    }
}

3. 二叉搜索树查找

BSTreeNode *BSearch(BSTreeNode *root, int target)
{
    if (NULL == root)
    {
        return NULL;
    }
    if (root->data == target)
    {
        return root;
    }else if (target > root->data)
    {
        return BSearch(root->right, target);
    }else{
        return BSearch(root->left, target);
    }
    return NULL;
}

4. 二叉搜索树删除

4.1 被删除节点分析

思考删除如下一个二叉搜索树的某个节点:

  1. 被删除节点无子结点,那么直接删除该节点就好了。例如图中的 0001 , 0005 , 0009 , 0014 , 0020
  2. 被删除节点只有一个左节点,例如图中的 0025 ,那么删除该节点,把左节点放在该节点就好了。
  3. 被删除节点只有一个右节点,和情况2是镜像关系。
  4. 被删除节点既有左节点,又有右节点,那么怎么删除呢?例如图中的 0004 , 0012 , 0015

以删除 0012 为例,有两种选择:一是删除 0012 ,将左子树上的节点 0009 提上来,放在 0012 的位置;二是将右子树上的节点 0014 放在 0012 的位置;

原因很简单,因为 00090012 左子树上的最大值;而 00140012 右子树上的最小值。

回忆下二叉树中序遍历,中序遍历二叉搜索书刚好是有序的,按照中序遍历, 0012 前面的一个节点是 0009 ,后面一个节点是 0014 ,故而 0009 叫做 0012 的前驱节点, 0014 叫做 0012 的后继节点;至于删除时候是用前驱还是后继,都是可以的。

4.2 寻找某节点的前驱节点

BSTreeNode *FindMax(BSTreeNode *root)
{
    if (NULL == root)
    {
        return NULL;
    }
    if (root->right == NULL)
    {
        return root;
    }else{
        return FindMin(root->right);
    }
}

4.3 寻找某节点的后继节点

BSTreeNode *FindMin(BSTreeNode *root)
{
    if (NULL == root)
    {
        return NULL;
    }
    if (root->left == NULL)
    {
        return root;
    }else{
        return FindMin(root->left);
    }
}

4.4 二叉搜索树删除

BSTreeNode *Delete(BSTreeNode *root, int target)
{
    if (NULL == root)
    {
        return NULL;
    }
    if (target > root->data)
    {
        root->right = Delete(root->right, target);
    }else if(target < root->data){
        root->left  = Delete(root->left, target);
    }else{
        //相等的情况
        struct BSTreeNode *tmp;
        if (root->left && root->right)
        {
            tmp = FindMin(root->right);
            root->data = tmp->data;
            root->right = Delete(root->right, root->data);
        }else{
            tmp = root;
            if (root->left == NULL)
            {
                root = root->right;
            }else if(root->right == NULL){
                root = root->left;
            }else{
                root = NULL;//删除自身
            }
        }
    }
    return root;
}

Done!