# 二叉排序树

## 二叉排序树(BST)

### 定义

  二叉排序树又称二叉查找树。二叉排序树或是一棵空树，或是一棵具有下列特性的非空二叉树：

  1）若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字值。

  2）若右子树非空，则右子树上所有结点关键字值均大于根结点的关键字值。

  3）左、右子树本身也分别是一棵二叉排序树

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/二叉排序树.jpg)

  左子树结点值 < 根结点值 < 右子树结点值，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

### 查找

  二叉排序树的查找是从根结点开始，沿某个分支逐层向下进行比较的过程。若二叉树非空，则将给定值与根结点的关键字比较；若相等，则查找成功；若不等，则当前结点的关键字值大于给定关键字值时，在根节点的左子树查找，否则在根节点的右子树中查找。这是一个递归的过程。

  二叉排序树的递归查找算法：

```cpp
BSTNode* BST_Search(BitTree T, ElemType key){
    if(T == NULL){
        return NULL;
    }
    if( T->data == key){
        return T;
    }else if( T->data > key){
        return BST_Search(T->lchild, key);
    }else if( T->data < key){
        return BST_Search(T->rchild, key);
    }
}
```

  二叉排序树的非递归查找算法：

```cpp
BSTNode* BST_Search(BitTree T, ElemType key, BSTNode* &p){
    p = NULL;
    while( T != NULL && key != T->data ){
        p = T;
        if( key < T->data ){
            T = T->lchild;
        }else{
            T = T->rchild;
        }
    }
    return T;
}
```

### 插入

  二叉排序树是一种动态几何，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字值等于给定值的结点时在进行插入的。

  由于二叉排序树是递归定义的，因此插入结点的过程如下：若二叉排序树为空，则直接插入结点；否则，若关键字k小于根结点关键字，则插入左子树，若关键字大于根结点关键字，则插入右子树。

```cpp
bool BST_Insert(BitTree& T, ElemType k){
    if( T == NULL){
        T = (BitTree*)malloc(sizeof(BitTree));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return true;
    }else if( T->data == k){    //树中存在相同关键字的结点
        return false;        
    }else if( k < T->key ){
        return BST_Insert(T->lchild, k);
    }else if( k > T->data ){
        return BST_Insert(T->rchild, k);
    }
    return true;
}
```

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/二叉排序树插入.png)

### 二叉排序树的构造

  构造一棵二叉树就是依次输入数据元素，并将它们插入二叉排序树中适当位置上的过程。具体过程：每读入一个元素，就建立一个结点，若二叉排序树非空，则将新结点的值与根结点的值作比较，若小于根结点的值，则插入左子树，否则插入右子树；若二叉排序树为空，则将新结点作为二叉排序树的根结点。

```cpp
void BST_Create(BitTree& T, ElemType str[]){
    int sz = sizeof(str)/sizeof(str[0]);
    T = NULL;
    int i = 0;
    while( i < sz ){
        Create_BST(T,str[i]);
        i++;
    }
}
```

### 删除（难点）

  在二叉排序树中删除一个结点时，不能把以结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。

  删除操作按三种情况来处理：

1. 若被删除结点 x 是叶结点，则直接删除，不会破坏二叉排序树的性质
2. 若结点 x 只有一棵左子树或右子树，则让 x 的子树成为 x 父节点 的子树，替代 x 的位置
3. 若结点 x 有左、右两棵子树，则令 x 的直接后继（或直接前驱）替代 x ，然后从二叉排序树中删除这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/二叉排序树删除.jpg)

```cpp
//中序遍历序列的下一个节点，即比当前节点大的最小节点，简称后继节点。
int successor(BSTTree* p){
    p = p->rchild;
    while(p->lchild != NULL){
        p = p->left;
    }
    return p->data;
}
//中序遍历序列的前一个节点，即比当前节点小的最大节点，简称前驱节点。 
int predecessor(BSTTree* p){
    p = p->lchild;
    while(p->rchild != NULL){
        p = p->rchild;
    } 
    return p->data;
}

BSTNode* BST_Delete(BSTTree& T, ElemType x){
    if( T == NULL){
        return NULL;
    }else{
        if( x < T->data ){    //要删除的在左边
            T->lchild = BST_Delete(T->lchild, x);
        }else if( x > T->data ){    //要删除的在右边
            T->rchild = BST_Delete(T->rchild, x);
        }else{
            if( T->lchild == NULL && T->rchild == NULL){//叶子结点
                T = NULL;
            }else if( T->rchild != NULL){
            //如果该节点不是叶子节点且有右节点，则用它的后继结点的值替代，然后删除后继结点               
                T->data = successor(T);
                T->rchild = BST_Delete(T->rchild, T->data);
            }else {
            //如果该节点不是叶子节点且只有左节点，则用它的前驱节点的值替代，然后删除前驱节点               
                T->data = predecessor(T);
                T->lchild = BST_Delete(T->lchild, T->data);                
            }
        }
    }
    return T;
}
```

### 二叉排序树的查找效率

  对于高度为h的二叉排序树，插入和删除操作的运行时间都是O(h)。但在最坏情况下，构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能新竹变坏，树的高度也增加为元素个数n。

  二叉排序树的查找算法平均查找长度，主要取决于树的高度，即与二叉树的形态有关。若退化成链表，则为O（n）;若为平衡二叉树，则为O（log2n)。

  相同的关键字其插入顺序不同可能生成不同的二叉排序树。

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/不同的二叉排序树.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://xiuxin.gitbook.io/datastructre/shu-he-er-cha-shu/er-cha-pai-xu-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.