二叉排序树

概念

二叉排序树 $Binary$ $Sort$ $Tree(BST)$, 也称二叉查找树

graph LR
    X(特点)
    X-->A(若左子树非空, 则左子树上所有结点值均小于其根结点值)
    X-->B(若右子树非空, 则右子树上所有结点值均大于其根结点值)
    X-->C(其左、右子树也是二叉排序树)
    X-->D(没有键值相等结点)

示例

graph TB
    N45((45))
        N45-->N11((11))
            N11-->N9((9))
            N11-->N23((23))
        N45-->N68((68))
            N68-->N76((76))

对该树进行中序遍历($LDR$)会得到一个递增有序序列: $9, 11, 23, 45, 50, 68, 76$

操作

查找

graph LR
    X(规则)
    X-->A(非空时查找根结点, 若与查找值相等则查找成功)
    X-->B(若与查找值不相等)
        B --> B1(查找值小于根结点值, 查找左子树)
        B --> B2(查找值大于根结点值, 查找右子树)
    X-->C(到叶节点仍未找到, 查找失败)

查找 $23$

graph TB
    N45(((45)))
        N45-->N11(((11)))
            N11-->N9((9))
            N11-->N23(((23)))
        N45-->N68((68))
            N68-->N76((76))

因为 $23 < 45$, 则查找左子树

因为 $23 > 11$, 则查找右子树, $23 = 23$, 查找成功

查找 $47$

graph TB
    N45(((45)))
        N45-->N11((11))
            N11-->N9((9))
            N11-->N23((23))
        N45-->N68(((68)))
            N68-->N76((76))

因为 $47 > 45$, 则查找右子树

因为 $47 < 68$, 则查找左子树, 左子树为空, 查找失败

递归写法

template<typename T>
struct BSTNode {
    T value;
    BSTNode<T> *leftSon;
    BSTNode<T> *rightSon;

    BSTNode(T value, BSTNode<T> *leftSon, BSTNode<T> *rightSon {
        this->value = value;
        this->leftSon = leftSon;
        this->rightSon = rightSon;
    }
};

template<typename T>
BSTNode<T> *Search(BSTNode<T> *root, const T value) {
    if (root == nullptr) {
        return nullptr;
    }

    if (root->value == value) {
        return root;
    }

    if (root->value > value) {
        return Search(root->lchind, value);
    }

    if (root->value < value) {
        return Search(root->rchind, value);
    }
}

非递归写法

template<typename T>
BSTNode<T> *Search(BSTNode<T> *root, const T value) {
    while(root != nullptr) {
        if (root->value == value) {
            return root;
        }

        if (root->value > value) {
            root = root->lchind;
        }

        if (root->value < value) {
            root = root->rchind;
        }
    }
    return nullptr;
}

插入

graph LR
    X(规则)
    X --> A(若二叉排序树为空, 直接插入结点)
    X --> B(若二叉排序树非空)
        B --> B1(插入值小于根结点时, 插入左子树)
        B --> B2(插入值大于根结点时, 插入右子树)
    X --> C(若插入值等于根结点时不进行插入)
    X --> D(新插入结点总是叶子结点)

插入 $15$

因为 $15 < 45$, 选择左子树,

因为 $15 > 11$, 选择右子树,

因为 $15 < 23$, 选择左子树, 左子树为空, 插入

graph TB
    N45(((45)))
        N45-->N11(((11)))
            N11-->N9((9))
            N11-->N23(((23)))
            N23-->N15(((15)))
        N45-->N68((68))
            
            N68-->N76((76))

// 返回构建完成后根节点
template<class T>
BSTNode<T> *AddNode(BSTNode<T> *root, const T value) {
    // 节点为空, 说明是叶子节点
    if(root == nullptr){
        root = new BSTNode<T>(value, nullptr, nullptr);
        return root;
    }

    // 值小于根结点时, 插入根节点左子树
    if(root->value > value) {
        root->leftSon = AddNode(root->leftSo, value);
    }

    // 值大于根结点时, 插入根节点右子树
    if(root->value < value) {
        root->rightSon = AddNode(root->rightSon, value);
    }
    return root;
}

构建

根节点为空, 进行插入操作

template<class T>
void Init(BSTNode<T> *root, vector<T> &v) {
    for(int i = 0, size = v.size(); i < size; i++) {
        root = AddNode(root, v[i]);
    }
}

删除

graph LR
    X(规则)
    X --> A(叶子结点直接删除)
    X --> B(若被删除结点 x 只有一个子树)
        B --> B1(让x子树成为 x 父结点的子树, 代替 x 结点)
    X --> C(若被删除结点x有两个子树)
        C --> C1(让x右子树中最小节点 y 代替 x, 并删除y)

删除 $9$ 节点

$9$ 节点是叶子节点, 直接删除

graph TB
    N45((45))
        N45 --> N11((11))
            N11 -.-> N9(((9)))
            N11 --> N23((23))
        N45 --> N68((68))
            N68 --> N76((76))

删除 $68$

$68$ 节点只有一个子树, 让 $68$ 子树 $76$, 成为 $68$ 父节点 $45$ 的子树

graph TB
    N45((45))
        N45 --> N11((11))
            N11 --> N9((9))
            N11 --> N23((23))
        N45 -.-> N68((68))
            N68 -.-> N76((76))

        N45 --> N76

graph TB
    N45((45))
        N45 --> N11((11))
            N11 --> N9((9))
            N11 --> N23((23))
        N45 --> N76((76))

删除 $11$

$11$ 右子树中最小节点为 $23$, 让 $23$ 代替 $11$

graph TB
    N45((45))
        N45-->N11((11))
            N11-->N9((9))
            N11-.->N23((23))
    
        N45-->N68((68))
            N68-->N76((76))
    N23-->N11

graph TB
    N45((45))
        N45-->N23((23))
            N23-->N9((9))
        N45-->N68((68))
            N68-->N76((76))

template<class T>
void DelNode(BSTNode<T> *root, const T value){
    if (root == nullptr) {
        return;
    }
    // p为待删除节点, fp为其父节点
    BSTNode<T> *p = root;
    BSTNode<T> *fp = root;

    while (p->value != value) {
        fp = p;
        if (p->value > value) {
            // 查找左子树
            p = p->leftSon;
        }

        if (p->value < value) {
            // 查找右子树
            p = p->rightSon;
        }
    }

    // 情况1, p为叶子节点, 直接删
    if (p->leftSon == nullptr && p->rightSon == nullptr) {
        if (fp->leftSon != nullptr) {
            fp->leftSon = nullptr;
        }

        if (fp->rightSon != nullptr) {
            fp->rightSon = nullptr;
        }

        delete(p);
        p = nullptr;

        return;
    }

    // 情况2, p左子树为空, 重接右子树
    if (p->leftSon == nullptr) {
        p->value = p->rightSon->value;
        p->rightSon = nullptr;

        delete(p);
        p = nullptr;

        return;
    }

    // 情况3, p右子树为空, 重接左子树
    if (p->rightSon == nullptr) {
        p->value = p->leftSon->value;

        delete(p->leftSon);
        p->leftSon = nullptr;

        return;
    }
    
    // 情况4, p左右子树均不为空时, 需要找p右子树中最小节点(最左节点)q
    BSTNode<T> *q = p->rightSon;
    // fq为q父节点
    BSTNode<T> *fq = q;
    // 循环查找左节点, 就会找到最小值
    while(q->leftSon != nullptr) {
        fq = q;
        q = q->leftSon;
    }
    fq->leftSon = nullptr;
    // 用最小值节点代替欲删除节点
    p->value = q->value;

    delete(q);
    q = nullptr;
    return;
}

遍历

// 中序遍历
template<class T>
void OutputBST(BSTNode<T> *root) {
    if (root->leftSon != nullptr) {
        OutputBST(root->leftSon);
    }

    std::cout << root->value << std::endl;

    if (root->rightSon != nullptr) {
        OutputBST(root->rightSon);
    }
}

下篇哈夫曼树