## 编程知识 cdmana.com

### Data structure and algorithm: insert / search / delete of C binary search tree

C Language implementation search Binary Tree

##### 1 Structure
``````typedef struct BSTreeNode {
int data; // Data fields
struct BSTreeNode *left; // Left child node
struct BSTreeNode *right; // Right child node
} BSTreeNode;``````
##### 2 Insert
``````//1. The first one is , Pass in the pointer , Return root node
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;
}
// The second kind   Pass in the secondary pointer , The pointer of the pointer , There is no need to return
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 lookup
``````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);
}
}``````

Stack and queue building See other blogs

##### 4 Delete
``````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{
// Equal case
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;// Delete yourself
}
}
}
return root;
}``````

test ：

Scroll to Top