C++二叉搜索树详解（从零开始实现二叉搜索树的完整教程）

C++二叉搜索树的基本结构

首先，我们需要定义树的节点结构。每个节点包含数据、指向左子节点和右子节点的指针。

struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    // 构造函数    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};

实现二叉搜索树类

接下来，我们封装一个 BST 类，包含插入、查找、删除等基本操作。

class BST {private:    TreeNode* root;    // 辅助函数：递归插入    TreeNode* insertHelper(TreeNode* node, int val) {        if (node == nullptr) {            return new TreeNode(val);        }        if (val < node->val) {            node->left = insertHelper(node->left, val);        } else if (val > node->val) {            node->right = insertHelper(node->right, val);        }        // 如果值相等，不插入重复值        return node;    }    // 辅助函数：查找最小值节点（用于删除操作）    TreeNode* findMin(TreeNode* node) {        while (node && node->left != nullptr) {            node = node->left;        }        return node;    }    // 辅助函数：递归删除    TreeNode* deleteHelper(TreeNode* node, int val) {        if (node == nullptr) return node;        if (val < node->val) {            node->left = deleteHelper(node->left, val);        } else if (val > node->val) {            node->right = deleteHelper(node->right, val);        } else {            // 找到要删除的节点            if (node->left == nullptr) {                TreeNode* temp = node->right;                delete node;                return temp;            } else if (node->right == nullptr) {                TreeNode* temp = node->left;                delete node;                return temp;            }            // 有两个子节点：找到右子树的最小值替换            TreeNode* temp = findMin(node->right);            node->val = temp->val;            node->right = deleteHelper(node->right, temp->val);        }        return node;    }    // 中序遍历（用于验证BST性质）    void inorderTraversal(TreeNode* node) {        if (node != nullptr) {            inorderTraversal(node->left);            std::cout << node->val << " ";            inorderTraversal(node->right);        }    }public:    BST() : root(nullptr) {}    void insert(int val) {        root = insertHelper(root, val);    }    void remove(int val) {        root = deleteHelper(root, val);    }    void inorder() {        inorderTraversal(root);        std::cout << std::endl;    }};

使用示例

下面是一个简单的使用示例，展示如何创建BST并进行基本操作：

#include <iostream>int main() {    BST tree;    tree.insert(50);    tree.insert(30);    tree.insert(70);    tree.insert(20);    tree.insert(40);    tree.insert(60);    tree.insert(80);    std::cout << "中序遍历结果（应为升序）: ";    tree.inorder(); // 输出: 20 30 40 50 60 70 80    tree.remove(20); // 删除叶子节点    std::cout << "删除20后: ";    tree.inorder();    tree.remove(30); // 删除有一个子节点的节点    std::cout << "删除30后: ";    tree.inorder();    tree.remove(50); // 删除有两个子节点的根节点    std::cout << "删除50后: ";    tree.inorder();    return 0;}

时间复杂度分析

在理想情况下（树接近平衡），插入、删除和查找的时间复杂度都是 O(log n)。但在最坏情况下（树退化成链表），时间复杂度会退化为 O(n)。这也是为什么在实际应用中常使用 AVL 树或红黑树等自平衡二叉搜索树。

总结

通过本教程，你已经掌握了如何用 C++ 实现一个基本的二叉搜索树。这是学习更高级数据结构的重要一步。希望这个C++二叉搜索树的实现教程对你有所帮助！如果你正在学习C++数据结构，建议多动手练习，并尝试扩展功能，比如添加查找最大值、树的高度计算等方法。

记住，掌握二叉搜索树实现不仅能提升你的编程能力，还能为你在面试和算法竞赛中打下坚实基础。继续加油，探索更多关于二叉搜索树教程的内容吧！