# 数据结构与算法 ：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;
}``````