关于数据结构和算法:数据结构与算法-C-二叉搜索树的插入查找删除

C 语言实现搜寻二叉树

1 构造体

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

2 插入

//1. 第一种，传入指针，返回根节点
BSTreeNode *insert2(BSTreeNode *root, int data)
{if (NULL == root)
    {
        struct BSTreeNode *node;
        node = (struct BSTreeNode *)malloc(sizeof(struct BSTreeNode));
        if (node == NULL)
        {printf("malloc error \n");
            return NULL;
        }
        node->data = data;
        node->right = NULL;
        node->left = NULL;
        
        printf("null %d \n", data);
        return node;
    }
    printf("%d vs %d  \n", data,root->data);
    if (data >= root->data)
    {root->right = insert2(root->right, data);
    }else{root->left = insert2(root->left, data);
    }
    return root;
}
// 第二种 传入二级指针，即指针的指针，无需返回
void insert(BSTreeNode **root, int data)
{if (NULL == *root)
    {printf("****ins isnull %d \n", data);
        *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);
    }
}

栈和队列的构建 详见其余博文

4 删除

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

BSTreeNode *Delete(BSTreeNode *root, int target)
{if (NULL == root)
    {return NULL;}
    printf("%d vs %d  \n", target,root->data);
    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;
}

测试：