在 C++ 中从二叉搜索树中删除节点

Jinku Hu 2021年11月29日 2021年10月2日
在 C++ 中从二叉搜索树中删除节点

本文将讲解如何在二叉搜索树数据结构 C++ 中实现一个删除节点的函数。

C++ 中删除二叉搜索树中的节点

二叉搜索树是一种二叉树,它在每个节点中存储一个键值。该键用于构建有序树,以便每个节点的键大于其左子树中的所有键,并小于其右子树中的所有键。

每个节点通常包含两个指向 leftright 节点的指针,但我们还添加了另一个指针来表示父节点,因为它更容易实现 remove 成员函数。

请注意,以下二叉搜索树实现仅包含最少的成员函数来演示节点删除操作。

BinSearchTree 类只能将 int 类型存储为键值。除了 remove 之外的大多数函数都使用递归,因此我们提供了相应的在内部调用的 private 成员函数。通常,从树中删除节点是比插入和搜索更复杂的操作,因为它涉及多种场景。

第一个也是最简单的场景是我们需要删除一个没有子节点的节点(因此称为叶子节点)。叶子节点可以被解除分配并将 nullptr 分配给其父节点的相应指针。

第二种情况是删除只有一个孩子的节点。后者可以通过将目标的父级连接到其子级来解决,然后我们可以释放关联的内存。

#include <iostream>

using std::cout; using std::cerr;
using std::endl; using std::string;

struct BSTreeNode {
    int key{};
    BSTreeNode *parent{};
    BSTreeNode *left{};
    BSTreeNode *right{};

} typedef BSTreeNode;

class BinSearchTree {
public:
    BinSearchTree() { root = nullptr; size = 0; };
    BinSearchTree(std::initializer_list<int> list);

    void insert(int k);
    BSTreeNode *find(int k);
    int remove(int k);
    void print();
    size_t getSize() const;

    ~BinSearchTree();

private:
    BSTreeNode *root;
    size_t size;

    void freeNodes(BSTreeNode *&rnode);
    void printTree(BSTreeNode *node);
    void insertNode(BSTreeNode *&rnode, int k, BSTreeNode *pnode);
    BSTreeNode **findNode(BSTreeNode *&rnode, int k);
};

BinSearchTree::BinSearchTree(std::initializer_list<int> list) {
    root = nullptr;
    size = 0;

    for (const auto &item : list) {
        insertNode(root, item, nullptr);
    }
}

BinSearchTree::~BinSearchTree() {
    freeNodes(root);
}

void BinSearchTree::freeNodes(BSTreeNode *&rnode) {
    if (rnode != nullptr) {
        freeNodes(rnode->left);
        freeNodes(rnode->right);
        delete rnode;
    }
}

BSTreeNode *BinSearchTree::find(const int k) {
    return *findNode(root, k);
}

BSTreeNode **BinSearchTree::findNode(BSTreeNode *&rnode, const int k) {
    if (rnode == nullptr)
        return nullptr;

    if (k == rnode->key)
        return &rnode;

    if (k < rnode->key)
        return findNode(rnode->left, k);
    else
        return findNode(rnode->right, k);
}

void BinSearchTree::print() {
    if (size > 0)
        printTree(root);
    else
        cout << "tree is empty!" << endl;
}

void BinSearchTree::printTree(BSTreeNode *rnode) {
    if (rnode != nullptr) {
        printTree(rnode->left);
        cout << rnode->key << "; ";
        printTree(rnode->right);
    }
}

void BinSearchTree::insert(const int k) {
    insertNode(root, k, nullptr);
}

void BinSearchTree::insertNode(BSTreeNode *&rnode, const int k, BSTreeNode *pnode) {
    if (rnode == nullptr) {
        rnode = new BSTreeNode;
        rnode->key = k;
        rnode->parent = pnode;
        rnode->left = nullptr;
        rnode->right = nullptr;
        size++;
    } else {
        if (k < rnode->key)
            insertNode(rnode->left, k, rnode);
        else if (k == rnode->key)
            return;
        else
            insertNode(rnode->right, k, rnode);
    }
}

size_t BinSearchTree::getSize() const {
    return size;
}

int BinSearchTree::remove(const int k) {
    auto ret = findNode(root, k);
    if (ret == nullptr)
        return -1;

    if (size == 1) {
        auto tmp = root;
        root = nullptr;
        delete tmp;
        size--;
        return 0;
    }

    if ((*ret)->left == nullptr && (*ret)->right == nullptr) {
        auto tmp = *ret;
        if ((*ret)->key < (*ret)->parent->key)
            (*ret)->parent->left = nullptr;
        else
            (*ret)->parent->right = nullptr;
        delete tmp;
        size--;
        return 0;
    }

    if ((*ret)->left != nullptr && (*ret)->right != nullptr) {
        auto leftmost = (*ret)->right;

        while (leftmost && leftmost->left != nullptr)
            leftmost = leftmost->left;

        (*ret)->key = leftmost->key;

        if (leftmost->right != nullptr) {
            leftmost->right->parent = leftmost->parent;
            auto tmp = leftmost->right;
            *leftmost = *leftmost->right;
            leftmost->parent->left = leftmost;
            delete tmp;
        } else {
            leftmost->parent->right = nullptr;
            delete leftmost;
        }

        size--;
        return 0;
    } else {
        if ((*ret)->left != nullptr) {
            auto tmp = *ret;
            *ret = (*ret)->left;
            (*ret)->parent = tmp->parent;
            delete tmp;
        } else {
            auto tmp = *ret;
            *ret = (*ret)->right;
            (*ret)->parent = tmp->parent;
            delete tmp;
        }

        size--;
        return 0;
    }
}

int main() {
    BinSearchTree bst =  {6, 5, 11, 3, 2, 10, 12, 4, 9};

    cout << "size of bst = " << bst.getSize() << endl;
    bst.print();
    cout << endl;

    bst.insert(7);
    bst.insert(8);
    cout << "size of bst = " << bst.getSize() << endl;
    bst.print();
    cout << endl;

    bst.remove(6);
    bst.remove(2);
    bst.remove(12);
    cout << "size of bst = " << bst.getSize() << endl;
    bst.print();
    cout << endl;

    return EXIT_SUCCESS;
}
size of bst = 9
2; 3; 4; 5; 6; 9; 10; 11; 12;
size of bst = 11
2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12;
size of bst = 8
3; 4; 5; 7; 8; 9; 10; 11;

最复杂的场景是目标节点有两个孩子。在这种情况下,我们需要正确连接节点并保留为二叉搜索树结构指定的元素顺序。我们需要用最小的 key 和目标右子树的一部分替换目标节点。

在最左边的地方找到具有最小键的节点。因此我们应该遍历右子树,直到到达这个节点。一旦找到节点,我们可以将其键分配给目标节点,然后尝试删除前一个节点,就好像它是一个具有单个子节点的节点。后者是由这个节点是给定子树中最左边的一个事实所暗示的。因此,它只能有一个 right 子节点或根本没有子节点。

这三个场景是在 remove 成员函数中单独的 if...else 块中实现的,但我们还包含额外的代码来检查某些极端情况,例如在树中找不到元素或删除最后一个节点时。请注意,remove 函数也可以递归方式实现。

Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn

相关文章 - C++ Data Structure