C++实现BST需定义节点结构，支持插入、查找、删除：插入递归比较值并挂载；查找用迭代法O(1)空间；删除分三类——无子节点直接删、单子节点替代、双子节点用右子树最小值替换并递归删该值。
用C++实现二叉搜索树（BST），核心是定义节点结构、支持插入、查找、删除三种基本操作，并保证左子树所有节点值
节点定义与基础结构
每个节点包含数据、左指针、右指针。推荐用指针管理内存，配合构造函数简化初始化：
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};
插入操作（递归实现）
从根开始比较：比当前节点小则递归插入左子树，大则插入右子树；遇到空位置就新建节点。
TreeNode* insertIntoBST(TreeNode* root, int val) { if (!root) return new TreeNode(val); if (val val) root->left = insertIntoBST(root->left, val); else root->right = insertIntoBST(root->right, val); return root;}
查找操作（迭代更简洁）
利用BST性质逐层向下，无需递归，空间复杂度O(1)：
立即学习“C++免费学习笔记（深入）”；
TreeNode* searchBST(TreeNode* root, int val) { while (root && root->val != val) { root = (val val) ? root->left : root->right; } return root;}
删除操作（分三类处理）
找到目标节点后：
无子节点：直接删，返回nullptr仅一个子节点：用子节点替代当前节点两个子节点：找右子树最小值（或左子树最大值）替换，再递归删除该最小值节点
TreeNode* deleteNode(TreeNode* root, int key) { if (!root) return nullptr; if (key val) root->left = deleteNode(root->left, key); else if (key > root->val) root->right = deleteNode(root->right, key); else { if (!root->left) return root->right; if (!root->right) return root->left; TreeNode* minRight = root->right; while (minRight->left) minRight = minRight->left; root->val = minRight->val; root->right = deleteNode(root->right, minRight->val); } return root;}
基本上就这些。注意所有操作都依赖BST的有序性，插入/删除后结构仍保持BST性质。实际使用时建议封装成class，加size、中序遍历等辅助接口会更实用。
以上就是C++如何实现一个二叉搜索树？（数据结构代码）的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1488587.html
微信扫一扫 
支付宝扫一扫 
