在 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