What is a binary search tree

  • If his left subtree is not empty, then all nodes in the left subtree are less than the value of its root
  • If his right subtree is not empty, then all values of his right subtree are greater than the values of his root
  • Its left and right subtrees are also binary search trees

Binary tree structure

typedef struct BiTNode{

    int data;

    struct BiTNode * lchild,*rchild;

}BiTNodfe,*BiTree;
Copy the code

Binary search tree insertion

Status InsertBST(BiTree * T, **int** key){ BiTree p; if (! SearchBST(*T, key, NULL,&p)) { BiTree tem = (BiTree)malloc(sizeof(BiTNode)); tem->data = key; tem->lchild = NULL; tem->rchild = NULL; if (p == NULL) { *T = tem; } else if(key > p->data){ p->rchild = tem; } else { p->lchild = tem; } return TRUE; } return FALSE; }Copy the code

Delete binary search tree

Deletion of binary trees we need to discuss several cases
  • 1. Leaf node deletion: only need to delete this node (left/right hysteresis of parent node)
  • 2. There is a left subtree and the right subtree is empty (just reassign the node to its own left subtree)
  • 3. There is a right subtree and the left subtree is empty (just reassign the node to its own right subtree)
  • 4. There are both left and right subtrees
    • 1. The middle order of binary search tree is ascending order
    • 2. Directly replace the deleted node with the precursor
      1. Move the precursor of the precursor node (if the precursor node is a right subtree, delete it directly; if the precursor node has a left subtree, just move the left subtree to the node)

1 is special 2, 3 so there are only two cases

Status Delete(BiTree * p){
    BiTree temp,s;
    if((*p)->lchild == NULL){
        temp = *p;
        *p = (*p)->rchild;
        free(temp);
    } else if((*p)->rchild == NULL){
        temp = *p;
        *p = (*p)->lchild;
        free(temp);
    } else {
        temp = *p;
        s = temp->lchild;  
        while (s->rchild) {
            temp = s;
            s= s->rchild;
        }
        (*p)->data = s->data;
        if (temp == (*p)) {
            temp->lchild = s->lchild;
        } else {
            temp->rchild = s->lchild;
        }
        free(s);
    }
    return TRUE;
}
Copy the code