C++二叉搜索树：从原理到实战

好的我们来学习二叉搜索树Binary Search Tree, BST在 C 中的基础实现。这是一种高效的数据结构用于存储和检索数据。二叉搜索树概述二叉搜索树是一种特殊的二叉树它满足以下性质每个节点都有一个关键值。左子树中所有节点的关键值都小于其父节点的关键值。右子树中所有节点的关键值都大于其父节点的关键值。左右子树本身也必须是二叉搜索树。这种结构使得查找、插入和删除操作的平均时间复杂度可以达到 $$O(\log n)$$。C 实现要点1. 节点结构定义使用结构体TreeNode表示树中的节点包含数据、指向左子树的指针和指向右子树的指针。struct TreeNode { int val; // 节点存储的值 TreeNode *left; // 指向左子树的指针 TreeNode *right; // 指向右子树的指针 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数 };2. 基本操作查找Search从根节点开始根据目标值与当前节点值的大小关系决定向左或向右子树搜索。TreeNode* search(TreeNode* root, int target) { if (root nullptr || root-val target) return root; // 找到或树为空 if (target root-val) return search(root-left, target); // 目标值小搜索左子树 else return search(root-right, target); // 目标值大搜索右子树 }插入Insert找到合适的空位置遵循 BST 规则插入新节点。TreeNode* insert(TreeNode* root, int val) { if (root nullptr) return new TreeNode(val); // 创建新节点 if (val root-val) root-left insert(root-left, val); // 插入左子树 else if (val root-val) root-right insert(root-right, val); // 插入右子树 return root; // 返回当前节点指针 }删除Delete删除操作需考虑三种情况无子节点直接删除。只有一个子节点用子节点替代。有两个子节点找到右子树的最小节点或左子树的最大节点替代被删节点再删除该节点。TreeNode* deleteNode(TreeNode* root, int key) { if (root nullptr) return root; // 树为空 if (key root-val) root-left deleteNode(root-left, key); // 在左子树删除 else if (key root-val) root-right deleteNode(root-right, key); // 在右子树删除 else { // 找到要删除的节点 // 情况1无子节点或只有一个子节点 if (root-left nullptr) { TreeNode* temp root-right; delete root; return temp; } else if (root-right nullptr) { TreeNode* temp root-left; delete root; return temp; } // 情况3有两个子节点 TreeNode* temp root-right; while (temp-left ! nullptr) temp temp-left; // 找到右子树的最小节点 root-val temp-val; // 用最小节点的值覆盖 root-right deleteNode(root-right, temp-val); // 删除那个最小节点 } return root; }时间复杂度分析查找、插入、删除平均时间复杂度 $$O(\log n)$$最坏情况树退化成链表$$O(n)$$。遍历中序遍历Inorder Traversal可以得到有序序列时间复杂度 $$O(n)$$。总结二叉搜索树是 C 数据结构学习中的重要内容理解其原理并掌握基本操作是实现更高级树结构如 AVL 树、红黑树的基础。请务必动手实践上述代码加深理解。