【数据结构与算法C++实现】0、对数器

**数据结构与算法 C++ 实现**

###1. 对数器####1.1 简介对数器是一种常见的数据结构，用于快速查找、插入或删除元素。它通常使用二叉树作为底层数据结构。

####1.2 实现

cpp#include <iostream>
using namespace std;

// 定义一个节点类struct Node {
 int data;
 Node* left;
 Node* right;
};

// 对数器类class BinarySearchTree {
private:
 Node* root; // 根节点public:
 // 构造函数 BinarySearchTree() : root(nullptr) {}

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

 // 插入元素 void insert(int data) {
 root = insertNode(root, data);
 }

 // 查找元素 bool find(int data) {
 return findNode(root, data);
 }

 // 删除元素 void remove(int data) {
 root = removeNode(root, data);
 }

private:
 // 插入节点函数 Node* insertNode(Node* node, int data) {
 if (node == nullptr) {
 node = new Node();
 node->data = data;
 node->left = node->right = nullptr;
 } else if (data < node->data) {
 node->left = insertNode(node->left, data);
 } else if (data > node->data) {
 node->right = insertNode(node->right, data);
 }
 return node;
 }

 // 查找节点函数 bool findNode(Node* node, int data) {
 if (node == nullptr) {
 return false;
 } else if (data < node->data) {
 return findNode(node->left, data);
 } else if (data > node->data) {
 return findNode(node->right, data);
 }
 return true;
 }

 // 删除节点函数 Node* removeNode(Node* node, int data) {
 if (node == nullptr) {
 return nullptr;
 } else if (data < node->data) {
 node->left = removeNode(node->left, data);
 } else if (data > node->data) {
 node->right = removeNode(node->right, data);
 } 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->data = minNode->data;
 node->right = removeNode(node->right, minNode->data);

 }
 return node;
 }

 // 销毁树函数 void destroyTree(Node* node) {
 if (node != nullptr) {
 destroyTree(node->left);
 destroyTree(node->right);
 delete node;
 }
 }

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

cppint 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.find(5) ? "是" : "否") << endl;
 cout << "是否存在元素9: " << (bst.find(9) ? "是" : "否") << endl;

 // 删除元素 bst.remove(3);
 cout << "是否存在元素3: " << (bst.find(3) ? "是" : "否") << endl;

 return0;
}