实现二分查找树，支持插入、删除、查询操作。
简介：实现二分查找树，支持插入、删除、查询操作。
算法思路
算法思路：
二分查找树是一种基于二叉树的数据结构，可以支持插入、删除和查询操作。
二分查找树中每个节点都具有以下性质：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身也必须是二叉搜索树。
在实现二分查找树的过程中，我们可以使用C++中的类来表示节点和树。具体而言，每个节点应包含如下属性：
- 当前节点的值 val；
- 当前节点的左子树 left；
- 当前节点的右子树 right。
在C++实现中还需要提供以下操作：
- 插入元素 insert；
- 删除元素 remove；
- 查询元素 find。
底层数据结构可以使用链表或数组均可。
下面是 C++ 中二分查找树的实现代码，每行都添加了详细注释：
#include <iostream> using namespace std; // 定义 Tree 类 struct Tree { int val; Tree* left; Tree* right; Tree(int v) { val = v; left = NULL; right = NULL; } }; // 定义 BST 类，封装树的所有操作 class BST { public: BST() { root = NULL; } // 初始化 void insert(int v) { // 插入元素 root = insertHelper(root, v); // 调用递归函数插入元素 } void remove(int v) { // 删除元素 root = removeHelper(root, v); // 调用递归函数删除元素 } bool find(int v) { // 查找元素 return findHelper(root, v); // 调用递归函数查找元素 } private: Tree* root; // 根节点 Tree* insertHelper(Tree* node, int val) { // 辅助函数，插入元素 if (!node) return new Tree(val); // 如果当前节点为空，则说明可以插入新的节点 if (val > node->val) node->right = insertHelper(node->right, val); else if (val < node->val) node->left = insertHelper(node->left, val); return node; } Tree* removeHelper(Tree* node, int val) { // 辅助函数，删除元素 if (!node) return NULL; // 如果当前节点为空，说明该元素不存在 if (val > node->val) node->right = removeHelper(node->right, val); else if (val < node->val) node->left = removeHelper(node->left, val); else { // 如果找到了要删除的元素 if (!node->left && !node->right) node = NULL; // 如果当前节点没有子节点，则直接删除 else if (node->left && !node->right) node = node->left; // 如果当前节点只有左子节点，则用左子节点代替当前节点 else if (node->right && !node->left) node = node->right; // 如果当前节点只有右子节点，则用右子节点代替当前节点 else { // 如果当前节点既有左子节点又有右子节点，则找到其右子树中的最小值，并将其作为新的根节点 Tree* minNode = getMin(node->right); node->val = minNode->val; node->right = removeHelper(node->right, minNode->val); // 从右子节点开始寻找最小值并删除 } } return node; } bool findHelper(Tree* node, int val) { // 辅助函数，查找元素 if (!node) return false; // 如果当前节点为空，说明该元素不存在 if (val == node->val) return true; else if (val > node->val) return findHelper(node->right, val); else return findHelper(node->left, val); } Tree*getMin(Tree* node) { // 辅助函数，获取当前二分查找树的最小值 while (node->left) { node = node->left; } return node; } }; int main() { BST tree; // 创建 BST 结构 tree.insert(4); // 插入元素 tree.insert(2); tree.insert(3); tree.insert(1); if (tree.find(3)) cout << "3 exists" << endl; // 查找元素，输出“3 exists” else cout << "3 does not exist" << endl; tree.remove(3); // 删除元素 if (tree.find(3)) cout << "3 exists" << endl; else cout << "3 does not exist" << endl; // 再次查找元素，输出“3 does not exist” return 0; }
在上述代码中，我们创建了 Tree 和 BST 两个数据结构，其中 Tree 表示树节点，BST 则封装了所有的二分查找树操作。具体而言，代码实现插入、删除和查找三个基本操作。
需要注意的是，在删除节点时，由于需要从源码中任意位置删除一个节点，因此需要考虑多种情况，例如节点只有一个儿子、节点没有儿子等情况。为了解决这些问题，我们可以采用递归方式依次寻找右子树的最小值。（当然也可以采用其他方式，比如迭代）。
- Java版本
class TreeNode { int val; // 节点存储的值 TreeNode left; // 左子节点 TreeNode right; // 右子节点 public TreeNode(int v) { val = v; left = null; right = null; } } class BST { TreeNode root; // 根节点 public BST() { root = null; } // 插入元素 public void insert(int val) { root = insertHelper(root, val); } // 删除元素 public void remove(int val) { root = removeHelper(root, val); } // 查找元素 public boolean find(int val) { return findHelper(root, val); } // 辅助函数，插入元素 private TreeNode insertHelper(TreeNode node, int val) { if (node == null) return new TreeNode(val); // 如果当前节点为空，则插入新节点 if (val > node.val) node.right = insertHelper(node.right, val); // 插入到右子树中 else if (val < node.val) node.left = insertHelper(node.left, val); // 插入到左子树中 return node; } // 辅助函数，删除元素 private TreeNode removeHelper(TreeNode node, int val) { if (node == null) return null; // 没有找到该节点 if (val > node.val) node.right = removeHelper(node.right, val); else if (val < node.val) node.left = removeHelper(node.left, val); else { // 找到删除的节点 if (node.left == null && node.right == null) // 没有左右子树，直接删除即可 node = null; else if (node.left != null && node.right == null) node = node.left; // 只有左子树，用左子树代替当前节点 else if (node.right != null && node.left == null) node = node.right; // 只有右子树，用右子树代替当前节点 else { // 左右子树都存在，寻找右子树中的最小值并用其代替当前节点 TreeNode minNode = getMin(node.right); node.val = minNode.val; node.right = removeHelper(node.right, minNode.val); } } return node; } // 辅助函数，查找元素 private boolean findHelper(TreeNode node, int val) { if (node == null) return false; // 未找到该节点 if (val == node.val) return true; else if (val > node.val) return findHelper(node.right, val); // 在右子树中查找 else return findHelper(node.left, val); // 在左子树中查找 } // 辅助函数，获取当前二分查找树的最小值 private TreeNode getMin(TreeNode node) { while (node.left != null) { node = node.left; } return node; } } public class Main { public static void main(String[] args) { BST tree = new BST(); // 创建 BST 结构 tree.insert(4); // 插入元素 tree.insert(2); tree.insert(3); tree.insert(1); if (tree.find(3)) System.out.println("3 exists"); // 查找元素，输出“3 exists” else System.out.println("3 does not exist"); tree.remove(3); // 删除元素 if (tree.find(3)) System.out.println("3 exists"); else System.out.println("3 does not exist"); // 再次查找元素，输出“3 does not exist” } }
在上述代码实现中，我们定义了 Tree 和 BST 类，其中 Tree 表示二分查找树的节点，BST 则封装了所有的操作。具体而言，代码实现了插入、删除和查找三个基本操作。
需要注意的是，在删除节点时需要考虑多种情况，例如节点只有一个儿子、节点没有儿子等情况。为了解决这些问题，我们可以采用递归方式依次寻找右子树的最小值，并将其作为新的根节点。（当然也可以使用其他搜索方法，比如迭代）。
