Learn-Algorithms/4 Tree/2-二叉查找树/二叉查找树.md

# 二叉查找树BST

二叉查找树（Binary search tree），也叫`有序二叉树(Ordered binary tree)`,`排序二叉树(Sorted binary tree)`。

是指一个空树或者具有下列性质的二叉树：
 
 1. 若任意节点的左子树不为空，则左子树上所有的节点值小于它的根节点值
 2. 若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
 3. 任意节点左右子树也为二叉查找树
 4. 没有键值(key)相等的节点


有序的二叉查找树，中序遍历结果是递增的。 `左小右大`


```
    typedef int ElemType;
    typedef struct BiSearchTree{
        ElemType key;
        struct BiSearchTree *lChild;
        struct BiSearchTree *rChild;
    }BiSearchTree;
    BiSearchTree *bisearch_tree_insert(BiSearchTree *tree,ElemType node);
    int bisearch_tree_delete(BiSearchTree **tree,ElemType node);
    int bisearch_tree_search(BiSearchTree *tree,ElemType node);
```


### 删除节点

删除节点,需要重建排序树

 1) 删除节点是叶子节点（分支为0），结构不破坏  
 2）删除节点只有一个分支(分支为1)，结构也不破坏  
 3）删除节点有2个分支，此时删除节点 ; 需要重建树  
 

思路一： 选左子树的最大节点，或右子树最小节点替换  
 
``` 
int bisearch_tree_delete(BiSearchTree **tree,ElemType node){
    
    if (NULL==tree) {
        return -1;
    } 
    // 查找删除目标节点
    BiSearchTree *target=*tree,*parent=NULL;
    while (NULL!=target) {
        if (node<target->key) {
            parent=target;
            target=target->lChild;
        }else if(node==target->key){
            break;
        }else{
            parent=target;
            target=target->rChild;
        }
    }
    
    if (NULL==target) {
        printf("树为空，或想要删除的节点不存在\n");
        return -1;
    }

    //该节点为叶子节点，直接删除
    if (!target->rChild && !target->lChild)
    {
        if (NULL==parent) {////只有一个节点的二叉查找树
            *tree=NULL;
        }else{
            if (target->key>parent->key) {
                parent->rChild=NULL;
            }else{
                parent->lChild=NULL;
            }
            
        }
        free(target);//父节点处理，不然野指针,造成崩溃
    }
    
    else if(!target->rChild){   //右子树空则只需重接它的左子树,用左子树替换掉当前要删除的节点
        BiSearchTree *del=target->lChild;
        target->key = target->lChild->key;
        target->lChild=target->lChild->lChild;
        target->rChild=target->lChild->rChild;
        
        free(del);
    }
    else if(!target->lChild){   //左子树空只需重接它的右子树
        BiSearchTree *del=target->rChild;
        target->key = target->rChild->key;
        target->lChild=target->rChild->lChild;
        target->rChild=target->rChild->rChild;
        
        free(del);
    } 

    else{   //左右子树均不空，p，t 2个指针一前以后，将左子树最大的节点(肯定是一个最右的节点)替换到删除的节点后，还需要处理左子树最大节点的左子树
        
        BiSearchTree *p=target,*t=target->lChild;
        while (t->rChild) {
            p = t;
            t=t->rChild;
        }// 找到左子树最大的，是删除节点的直接“前驱”
        
        target->key = t->key;
        
        if (p!=target) {
            p->rChild = t->lChild;
        }else{
            target->lChild = t->lChild;
        }
        
        free(t);
    }
        return 0;
    }
```