C++实现二叉搜索树（BST），通过控制台能够实现增删改查

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树结构，它的每个节点都包含一个键（key）、一个关联的值、一个指向左子树的指针和一个指向右子树的指针。在二叉搜索树中，对于任何节点，其左子树中的所有节点的键都小于该节点的键，而右子树中的所有节点的键都大于该节点的键。这种特性使得二叉搜索树非常适合进行查找、插入和删除操作。 在C++中实现二叉搜索树，首先需要定义一个表示节点的数据结构，一般包括键值、指针到左右子节点以及可能需要的额外信息，例如存储的值或用于链接的指针。以下是一个简单的节点定义： ```cpp struct TreeNode { int key; TreeNode* left; TreeNode* right; TreeNode(int k) : key(k), left(nullptr), right(nullptr) {} }; ``` 接着，我们可以创建一个BST类，它将包含增删改查等操作的方法。例如，插入一个新节点可以使用递归的方式实现，如下所示： ```cpp class BST { public: void insert(int key) { root = _insert(root, key); } private: TreeNode* _insert(TreeNode* node, int key) { if (node == nullptr) { return new TreeNode(key); } if (key < node->key) { node->left = _insert(node->left, key); } else if (key > node->key) { node->right = _insert(node->right, key); } return node; } TreeNode* root; }; ``` 删除操作相对复杂，因为它可能涉及三种情况：要删除的节点是叶子节点、只有一个孩子或者有两个孩子。这里仅展示删除节点的基本思路： ```cpp void deleteNode(int key) { root = _deleteNode(root, key); } TreeNode* _deleteNode(TreeNode* node, int key) { // ... 实现删除逻辑 ... } ``` 查询节点是否存在可以通过递归的搜索实现： ```cpp TreeNode* search(int key) { return _search(root, key); } TreeNode* _search(TreeNode* node, int key) { if (node == nullptr || node->key == key) { return node; } return key < node->key ? _search(node->left, key) : _search(node->right, key); } ``` 计算树的高度可以采用递归的方式，每次比较左右子树的高度并取较大者： ```cpp int height() { return _height(root); } int _height(TreeNode* node) { if (node == nullptr) { return 0; } return 1 + max(_height(node->left), _height(node->right)); } ``` 在实际项目中，你可能会遇到更复杂的需求，例如平衡二叉搜索树（AVL或红黑树）以保持高度平衡，或者使用迭代而非递归的方式来优化性能。在提供的压缩包文件"P10_Peifan_Tian"中，可能包含了实现这些功能的源代码示例，你可以通过查看和学习这些代码来深入了解C++实现二叉搜索树的具体细节。