【C++】二叉搜索树

**二叉搜索树**

二叉搜索树（Binary Search Tree）是计算机科学中一个重要的数据结构。它是一种特殊的二叉树，每个结点最多有两个子结点，分别称为左孩子和右孩子。二叉搜索树的定义如下：

* 每个结点都有一个键（key），这个键是唯一的。
* 左孩子的所有键都小于父结点的键。
* 右孩子的所有键都大于父结点的键。

**二叉搜索树的特性**

二叉搜索树具有以下几个重要的特性：

1. **查找时间复杂度为O(h)**：其中h是树的高度。最坏情况下，树是完全不平衡的，这时查找时间复杂度为O(n)，n是结点的数量。
2. **插入和删除操作的平均时间复杂度为O(log n)**：当树是平衡的时，插入和删除操作的平均时间复杂度为O(log n)。
3. **查找、插入和删除等操作都可以在O(1)的时间内完成**：如果我们使用一个额外的数组来存储结点的键值，这样就可以在O(1)的时间内找到或插入或删除一个结点。

**二叉搜索树的应用**

二叉搜索树有很多应用：

* **数据库索引**：许多数据库系统使用二叉搜索树作为索引结构，来快速查找和检索数据。
* **文件系统**：一些文件系统也使用二叉搜索树来组织文件和目录的结构。
* **编译器**：在编译器中，二叉搜索树可以用来存储符号表（symbol table），即变量名与其对应值之间的映射关系。

**C++实现**

下面是C++中一个简单的二叉搜索树的实现：

cpp#include <iostream>
using namespace std;

// 结点结构体struct Node {
 int key;
 Node* left;
 Node* right;
};

// 二叉搜索树类class BinarySearchTree {
public:
 // 构造函数 BinarySearchTree() : root(nullptr) {}

 // 销毁函数 ~BinarySearchTree() { destroyTree(root); }

 // 插入函数 void insert(int key) {
 if (root == nullptr) {
 root = new Node();
 root->key = key;
 root->left = root->right = nullptr;
 } else {
 insertNode(key, root);
 }
 }

 // 查找函数 bool search(int key) {
 return searchNode(key, root);
 }

 // 删除函数 void remove(int key) {
 root = removeNode(key, root);
 }

private:
 Node* root;

 // 插入结点函数 void insertNode(int key, Node*& node) {
 if (key < node->key) {
 if (node->left == nullptr) {
 node->left = new Node();
 node->left->key = key;
 node->left->left = node->left->right = nullptr;
 } else {
 insertNode(key, node->left);
 }
 } else if (key > node->key) {
 if (node->right == nullptr) {
 node->right = new Node();
 node->right->key = key;
 node->right->left = node->right->right = nullptr;
 } else {
 insertNode(key, node->right);
 }
 }
 }

 // 查找结点函数 bool searchNode(int key, Node* node) {
 if (node == nullptr) return false;

 if (key < node->key) {
 return searchNode(key, node->left);
 } else if (key > node->key) {
 return searchNode(key, node->right);
 }

 return true;
 }

 // 删除结点函数 Node* removeNode(int key, Node* node) {
 if (node == nullptr) return nullptr;

 if (key < node->key) {
 node->left = removeNode(key, node->left);
 } else if (key > node->key) {
 node->right = removeNode(key, node->right);
 } else {
 // 删除结点 if (node->left == nullptr && node->right == nullptr) {
 delete node;
 return nullptr;
 }

 if (node->left == nullptr) {
 Node* temp = node->right;
 delete node;
 return temp;
 }

 if (node->right == nullptr) {
 Node* temp = node->left;
 delete node;
 return temp;
 }

 // 找到最小结点 Node* minNode = findMin(node->right);
 node->key = minNode->key;

 // 删除最小结点 node->right = removeNode(minNode->key, node->right);
 }

 return node;
 }

 // 销毁函数 void destroyTree(Node* node) {
 if (node == nullptr) return;

 destroyTree(node->left);
 destroyTree(node->right);

 delete node;
 }

 // 找到最小结点函数 Node* findMin(Node* node) {
 while (node->left != nullptr) {
 node = node->left;
 }
 return node;
 }
};

int main() {
 BinarySearchTree bst;

 bst.insert(5);
 bst.insert(3);
 bst.insert(7);
 bst.insert(2);
 bst.insert(4);
 bst.insert(6);
 bst.insert(8);

 cout << "是否存在5: " << (bst.search(5) ? "Yes" : "No") << endl;
 cout << "是否存在9: " << (bst.search(9) ? "Yes" : "No") << endl;

 bst.remove(5);
 cout << "是否存在5: " << (bst.search(5) ? "Yes" : "No") << endl;

 return0;
}