C++二叉搜索树查找，插入，删除

二叉搜索树（Binary Search Tree, BST）是一种二叉树，每个节点包含一个键值，并且具有以下特性：

左子树的所有节点的键值都小于当前节点的键值。
右子树的所有节点的键值都大于当前节点的键值。
每个节点的左右子树都是二叉搜索树。

在BST中，查找、插入和删除操作的时间复杂度通常为 (O(\log n))，其中 (n) 是树中的节点数。这是因为在理想情况下，树的高度是对数级别的。

接下来我将写一个基本的二叉搜索树实现，包括查找、插入和删除操作，并说明其原理。

查找操作

查找操作是根据键值在树中查找目标节点。由于BST的特性，可以根据目标键值与当前节点键值的比较，决定是向左子树还是右子树递归查找。

插入操作

插入操作是通过查找空位置来插入新的节点。首先从根节点开始，沿着树的路径向下查找，找到一个空位置后插入节点。

删除操作

删除操作分为三种情况：

删除的节点是叶子节点：直接删除该节点。
删除的节点有一个子节点：将该节点的父节点指向其唯一的子节点。
删除的节点有两个子节点：此时我们找到该节点的中序后继节点（右子树中最小的节点），用它的值替代被删除节点的值，然后删除后继节点。

C++代码实现

#include <iostream>
using namespace std;// 二叉搜索树节点结构
struct TreeNode {int value;TreeNode* left;TreeNode* right;TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};// 查找操作
TreeNode* search(TreeNode* root, int key) {if (root == nullptr || root->value == key)return root;if (key < root->value)return search(root->left, key);elsereturn search(root->right, key);
}// 插入操作
TreeNode* insert(TreeNode* root, int key) {if (root == nullptr)return new TreeNode(key);if (key < root->value)root->left = insert(root->left, key);elseroot->right = insert(root->right, key);return root;
}// 删除操作
TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root;if (key < root->value)root->left = deleteNode(root->left, key);else if (key > root->value)root->right = deleteNode(root->right, key);else {// 如果节点只有一个子树或者没有子树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;}// 如果节点有两个子树TreeNode* temp = minValueNode(root->right); // 找到右子树的最小节点root->value = temp->value; // 替换值root->right = deleteNode(root->right, temp->value); // 删除后继节点}return root;
}// 查找右子树最小的节点
TreeNode* minValueNode(TreeNode* node) {TreeNode* current = node;while (current && current->left != nullptr)current = current->left;return current;
}// 中序遍历
void inorder(TreeNode* root) {if (root != nullptr) {inorder(root->left);cout << root->value << " ";inorder(root->right);}
}int main() {TreeNode* root = nullptr;// 插入一些节点root = insert(root, 50);root = insert(root, 30);root = insert(root, 20);root = insert(root, 40);root = insert(root, 70);root = insert(root, 60);root = insert(root, 80);cout << "中序遍历结果：";inorder(root);cout << endl;// 查找节点TreeNode* found = search(root, 40);if (found != nullptr)cout << "找到节点： " << found->value << endl;elsecout << "未找到节点" << endl;// 删除节点root = deleteNode(root, 20);cout << "删除节点 20 后的中序遍历：";inorder(root);cout << endl;return 0;
}

代码解析

查找操作：从根节点开始，如果要查找的键值比当前节点小，则向左子树递归查找；如果大于当前节点，则向右子树递归查找。时间复杂度是 (O(\log n))，因为树的高度为对数级别。
插入操作：插入时同样从根节点开始，找到合适的位置（空位置），然后插入节点。时间复杂度同样是 (O(\log n))。
删除操作：
- 当删除的节点只有一个子节点或没有子节点时，直接删除该节点并连接父节点。
- 当删除的节点有两个子节点时，找到该节点的中序后继（右子树最小节点），将其值替代删除节点的值，然后删除中序后继节点。
中序遍历：中序遍历BST会得到从小到大的节点值。