RodneyX

BST，即二叉搜索樹，該數據結構規定任意若一個結點存在左子樹，那么該結點鍵必須要大于左子樹上所有鍵；若有右子樹，那么該結點鍵必須要小于右子樹上所有鍵

簡單的BST是樹形查找里的入門級數據結構，不涉及平衡性調節，只需要簡單插入刪除，即可，其中刪除稍復雜，但是也不難，只需要把三種情況分清即可。簡單的BST因為不存在平衡調節，所以針對某些特定序列(如已排序序列依次插入)在構造好BST后，事實上退化為鏈表，這樣搜索效率大幅下降到O(n)

今天先貼個簡單BST實現，改天再貼個AVL樹的實現

typedef struct BSTnode {
    struct BSTnode *left, *right;
    int data;
}BSTnode, *BST;

//simple BST
BST batch_create_BST(int a[], int n);
void destroy_BST(BST &T);
bool insert_BST(BST &T, int e);
bool delete_BST(BST &T, int e);
bool find_BST(BST &T, int e);

BST batch_create_BST(int a[], int n)
{
    BST T = nullptr;
    for (int i = 0; i < n; ++i)
        insert_BST(T, a[i]);
    return T;
}

void destroy_BST(BST &T)
{
    if (!T)
        return;
    destroy_BST(T->left);
    destroy_BST(T->right);
    free(T);
    T = nullptr;
}

bool insert_BST(BST &T, int e)
{
    if (!T)
    {
        T = (BSTnode *)malloc(sizeof(BSTnode));
        T->data = e;
        T->left = T->right = nullptr;
        return true;
    }
    if (e > T->data)
        return insert_BST(T->right, e);
    else if (e < T->data)
        return insert_BST(T->left, e);
    return false;
}

bool delete_BST(BST &T, int e)
{
    if (!T) // 空樹刪除失敗
        return false;
    if (T->data == e) // 特殊處理根節點刪除
    {
        if (T->left && T->right) // 根有左右子樹
        {
            BSTnode *p = T, *q = T->left;
            while (q->right) // 找到根節點的前驅以及前驅的父結點
            {
                p = q;
                q = q->right;
            }
            T->data = q->data; // 覆蓋根的元素
            // 以下刪除q
            if (p->left == q)
                p->left = q->left != nullptr ? q->left : q->right; // 這里可以處理葉節點情況
            else
                p->right = q->left != nullptr ? q->left : q->right; // 同上
            free(q);
            q = nullptr;
        }
        else // 僅有左或右子樹以及葉結點情況
        {
            BSTnode *del = T;
            T = T->left != nullptr ? T->left : T->right; // 事實上這里也能處理單節點情況
            free(del);
            del = nullptr;
        }
    }
    else // 刪除內部結點
    {
        BSTnode *p = nullptr, *q = T;
        while (q && q->data != e) // 查找待刪除結點及其父結點
        {
            p = q;
            q = q->data > e ? q->left : q->right;
        }
        if (!q) // 沒有這個結點刪除失敗
            return false;
        if (q->left && q->right) // 具有左右子樹的結點刪除
        {
            BSTnode *pre = q, *del = q->left;
            while (del->right) // 尋找待刪除結點的中序直接前驅以及這個前驅的父結點
            {
                pre = del;
                del = del->right;
            }
            q->data = del->data; // 前驅直接覆蓋原本待刪除結點
            // 以下刪除del
            if (pre->left == del)
                pre->left = del->left != nullptr ? del->left : del->right; // 可以處理葉結點情況
            else
                pre->right = del->left != nullptr ? del->left : del->right;
            ; // 同上
            free(del);
            del = nullptr;
        }
        else    // 僅有單子樹的結點或葉結點刪除
        {
            if (p->left == q)
                p->left = q->left != nullptr ? q->left : q->right; // 根據這里可以將前面的葉結點刪除作優化掉
            else
                p->right = q->left != nullptr ? q->left : q->right; // 同上
            free(q);
            q = nullptr;
        }
    }
    return true;
}

bool find_BST(BST &T, int e)
{
    BSTnode *p = T;
    while (p)
    {
        if (e > p->data)
            p = p->right;
        else if (e < p->data)
            p = p->left;
        else
            break;
        ;
    }
    if (p)
        return true;
    else
        return false;
}