C++数据结构之二叉搜索树的实现详解

1. 什么是二叉搜索树？

二叉搜索树是一种二叉树，其中每个节点都包含一个键值，且每个节点的键值都大于其左子树中任何节点的键值，小于其右子树中任何节点的键值。如下图所示：

        9
       / \
      4   15
         /  \
       12    20

在上面的二叉搜索树中，节点的键值分别是9, 4, 15, 12, 20，且每个节点的键值都符合上述定义。

2. 为什么需要二叉搜索树？

二叉搜索树可以支持快速的“查找”、“插入”和“删除”操作。这些操作均具有较低的时间复杂度，因此，二叉搜索树经常被用于需要高效查找、插入和删除操作的场合。

3. 二叉搜索树的实现

3.1 节点的定义

从二叉搜索树的定义可以看出，每个节点包含一个键值，因此，我们需要一个节点的结构体。对于每个节点，我们需要记录其键值，以及其左右子节点的指针。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

3.2 实现“插入”操作

插入操作是将一个新节点插入到二叉搜索树中。要插入新节点，我们需要遍历二叉搜索树，找到一个合适的位置，使得新节点的键值满足二叉搜索树的定义。

class BST {
public:
    TreeNode* insert(int val) {
        if (root_ == nullptr) {
            root_ = new TreeNode(val);
            return root_;
        }
        TreeNode* p = root_;
        while (true) {
            if (val < p->val) {
                if (p->left == nullptr) {
                    p->left = new TreeNode(val);
                    return p->left;
                }
                p = p->left;
            } else {
                if (p->right == nullptr) {
                    p->right = new TreeNode(val);
                    return p->right;
                }
                p = p->right;
            }
        }
    }

private:
    TreeNode* root_ = nullptr;
};

在这段代码中，我们使用指针变量p来遍历二叉搜索树，找到合适的插入位置。如果val小于p的键值，则将p的指针移动到其左子节点，否则将其指针移动到右子节点，直到找到需要插入节点的位置。如果根节点为空，则直接在根节点处插入新节点。

3.3 实现“查找”操作

查找操作可以在二叉搜索树中查找一个键值是否存在。这也需要遍历二叉搜索树，查找对应的节点。

class BST {
public:
    bool search(int val) {
        TreeNode* p = root_;
        while (p != nullptr) {
            if (p->val == val)
                return true;
            if (p->val > val)
                p = p->left;
            else
                p = p->right;
        }
        return false;
    }

private:
    TreeNode* root_ = nullptr;
};

在这段代码中，我们使用指针变量p来遍历二叉搜索树，找到对应的节点。如果当前节点的键值等于目标值，则返回true；否则，根据键值的大小关系，将p的指针移动到左右子节点。

3.4 实现“删除”操作

删除操作可以将二叉搜索树中的某个节点删除。删除节点有三种情况：对应节点没有子节点、对应节点只有一个子节点、对应节点有两个子节点。我们需要针对这三种情况来进行删除操作。

class BST {
public:
    void deleteNode(int val) {
        TreeNode* cur = root_;
        TreeNode* pre = nullptr;
        while (cur != nullptr && cur->val != val) {
            pre = cur;
            if (cur->val < val)
                cur = cur->right;
            else
                cur = cur->left;
        }
        if (cur == nullptr)
            return;
        if (cur->left != nullptr && cur->right != nullptr) {
            TreeNode* t = cur->right;
            while (t->left != nullptr)
                t = t->left;
            cur->val = t->val;
            cur = t;
            pre = cur->right;
        }
        TreeNode* c;
        if (cur->left != nullptr)
            c = cur->left;
        else
            c = cur->right;
        if (cur == root_)
            root_ = c;
        else if (pre->left == cur)
            pre->left = c;
        else
            pre->right = c;
        delete cur;
    }

private:
    TreeNode* root_ = nullptr;
};

在这段代码中，我们使用指针变量cur和pre来遍历二叉搜索树，找到对应的节点。如果当前节点有两个子节点，则用其右子树的最左节点来替换当前节点，并将删除操作转换为删除该最左节点的操作。如果当前节点只有一个子节点，则将其子节点指针赋值给当前节点的父节点。如果当前节点没有子节点，则直接将其删除。

4. 示例

4.1 示例一：从数组构建二叉搜索树

int main() {
    vector<int> nums = {9, 4, 15, 12, 20};
    BST bst;
    for (int num : nums)
        bst.insert(num);
    cout << bst.search(12) << endl; // 1
    cout << bst.search(19) << endl; // 0
    bst.deleteNode(15);
    cout << bst.search(15) << endl; // 0
    return 0;
}

在这个示例中，我们使用BST类来实现二叉搜索树的操作。首先将数组nums插入到二叉搜索树中，然后查找数值为12的节点是否存在，结果为1；查找数值为19的节点是否存在，结果为0。最后删除键值为15的节点，并再次查找，结果为0。

4.2 示例二：从文件构建二叉搜索树

int main() {
    ifstream infile;
    infile.open("data.txt");
    if (!infile) {
        cout << "Error: file not found" << endl;
        return 0;
    }
    BST bst;
    int num;
    while (infile >> num)
        bst.insert(num);
    infile.close();
    cout << bst.search(7) << endl; // 1
    return 0;
}

在这个示例中，我们从文件中读取数字，然后插入到二叉搜索树中。在本例中，数据存储在data.txt文件中。最后查找数值为7的节点是否存在，结果为1。