实验二 编写具体函数实现以下四种具体操作： （1）二叉排序树的递归查找 （2）二叉排序树的插入 （3）二叉排序树的创建 （4）二叉排序树的删除

好的，实验二主要是针对二叉排序树的相关操作进行编写，包括递归查找、插入、创建和删除四种具体操作。

1. 二叉排序树的递归查找：通过递归遍历二叉排序树，判断要查找的值是否等于当前节点的值，如果等于则返回该节点，否则判断要查找的值是在当前节点的左子树还是右子树，然后继续递归查找。

2. 二叉排序树的插入：从根节点开始遍历，找到要插入的位置，如果该位置为空，则新建一个节点并插入到该位置，否则继续遍历到下一层。

3. 二叉排序树的创建：通过读入一组数据，依次插入到二叉排序树中来创建一个二叉排序树。

4. 二叉排序树的删除：首先在二叉排序树中查找要删除的节点，如果该节点有两个子节点，则将其右子树中最小的节点（即右子树中最左边的节点）替换该节点，并将该节点删除。如果该节点只有一个子节点，则将该子节点替换该节点，并将该节点删除。如果该节点没有子节点，则直接删除该节点。

相关问题

根据二叉排序树的抽象数据类型的定义，使用二叉链表实现一个二叉排序树。 二叉排序树的基本功能： •二叉排序树的建立 2、二叉排序树的查找 3、二叉排序树的插入 4、 二叉排序树的删除 5、 二叉排序树的销毁 6、其他：自定义操作 编写测试 main()函数测试二叉排序树的正确性。

<<
二叉排序树（Binary Search Tree, BST）是一种特殊的二叉树，其中每个节点的值大于其左子树中所有节点的值，并且小于其右子树中所有节点的值。这使得在二叉排序树中查找、插入和删除元素变得非常高效。

**根据二叉链表实现二叉排序树的步骤：**

1. **二叉排序树的建立** (Insertion):
- 创建一个空链表作为根节点。
- 当接收到新元素时，从根节点开始比较，如果新元素小于当前节点，向左子链表插入；如果新元素大于当前节点，向右子链表插入。递归这个过程直到找到合适的位置。

2. **二叉排序树的查找** (Traversal):
- 从根节点开始，对比目标值与节点值，如果相等则返回该节点，如果不等则根据大小关系继续在左或右子链表中查找。

3. **二叉排序树的插入** (Insertion):
- 删除操作分为三类：删除叶子节点、删除只有一个子节点的非叶子节点和删除有两个子节点的非叶子节点。需考虑替换、旋转等复杂情况。

5. **二叉排序树的销毁** (Deletion of the tree):
- 可以通过中序遍历二叉树，对每个节点执行析构操作，释放内存。

6. **自定义操作** (Custom Operations):
- 可以实现如最小值、最大值、前驱后继节点查找、范围查找等高级操作。

**测试main()函数**:
- 创建一个二叉排序树实例。
- 遍历并打印树中的所有元素，检查是否按顺序排列。
- 插入元素，检查是否成功插入。
- 查找特定元素，确认能否找到。
- 删除元素并再次验证结构的正确性。
- 对树执行自定义操作，验证结果。

测试代码示例：

// 假设BSTNode是一个包含值、左指针和右指针的链表节点结构体
BSTNode* createBST(BSTNode* root, int value) {
    // 插入实现省略
}

BSTNode* searchBST(BSTNode* root, int value) {
    // 查找实现省略
}

BSTNode* deleteBST(BSTNode* root, int value) {
    // 删除实现省略
}

void destroyBST(BSTNode* root) {
    if (root) {
        destroyBST(root->left);
        destroyBST(root->right);
        delete root;
    }
}

int main() {
    BSTNode* root = nullptr; // 初始化为空
    // 创建树、插入元素、查找元素、删除元素
    // 执行自定义操作
    // 检查main结束时，销毁BST
    return 0;
}

根据二叉排序树的抽象数据类型的定义，使用二叉链表实现一个二叉排序树，并编写main()函数测试二叉排序树的正确性。 二叉排序树的基本功能： 二叉排序树的建立； 二叉排序树的查找； 二叉排序树的插入； 二叉排序树的删除； 二叉排序树的销毁；

### 实现二叉排序树（BST）

#### 创建节点

为了实现二叉排序树，首先定义一个表示树节点的数据结构：

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

此结构体用于存储每个节点的值及其左子节点和右子节点指针。

#### 查找操作

查找特定值的过程是从根节点开始，如果目标值小于当前节点，则进入左子树；反之则进入右子树。该过程持续到找到匹配项或到达叶子节点为止[^2]。

TreeNode* search(TreeNode* root, int target) {
    while (root != nullptr && root->value != target) {
        if (target < root->value)
            root = root->left;
        else
            root = root->right;
    }
    return root; // 返回指向目标结点的指针，未找到返回nullptr
}

#### 插入操作

插入新元素遵循与查找相似的原则，但在遇到第一个空位置时停止，并在此处放置新的节点。这保证了树保持其属性不变[^3]。

void insert(TreeNode*& root, int key) {
    if (!root) { // 如果当前位置为空，则创建一个新的节点
        root = new TreeNode(key);
        return;
    }

    if (key < root->value)
        insert(root->left, key); // 向左递归调用
    else if (key > root->value)
        insert(root->right, key); // 向右递归调用
}

#### 删除操作

删除分为三种情况处理：被删节点无子女、仅有一个孩子以及有两个孩子的情况。对于最后一种情形，通常会寻找待移除节点右侧最小值来替代它[^1]。

TreeNode* minValueNode(TreeNode* node) {
    TreeNode* current = node;
    while (current && current->left != nullptr)
        current = current->left;
    return current;
}

void deleteNode(TreeNode*& root, int key) {
    if (!root) return;

    if (key < root->value)
        deleteNode(root->left, key);
    else if (key > root->value)
        deleteNode(root->right, key);
    else {
        if (!root->left || !root->right) { // 只有单侧分支或没有分支
            TreeNode *temp = root->left ? root->left : root->right;
            if (!temp) temp = root; // 没有任何孩子的特殊情况
            free(root);
            root = temp;
        } else { // 存在两个孩子的情形
            TreeNode* temp = minValueNode(root->right);
            root->value = temp->value;
            deleteNode(root->right, temp->value);
        }
    }
}

#### 销毁整棵树

释放所有分配给节点的空间是一个重要的清理工作，可以通过后序遍历来完成这一任务。

void destroyTree(TreeNode*& root) {
    if (root == nullptr) return;
    
    destroyTree(root->left);
    destroyTree(root->right);

    delete root;
    root = nullptr;
}

#### 主函数测试

下面提供了一个简单的`main()`函数用来验证上述方法的功能是否正常运作。

#include <iostream>
using namespace std;

int main() {
    TreeNode* bstRoot = nullptr;

    // 测试插入功能
    cout << "Inserting elements into BST..." << endl;
    insert(bstRoot, 50);
    insert(bstRoot, 30);
    insert(bstRoot, 70);
    insert(bstRoot, 20);
    insert(bstRoot, 40);
    insert(bstRoot, 60);
    insert(bstRoot, 80);

    // 测试查找功能
    cout << "\nSearching for element 40:" << ((search(bstRoot, 40)) ? "Found" : "Not Found") << endl;

    // 测试删除功能
    cout << "\nDeleting element 20 from BST." << endl;
    deleteNode(bstRoot, 20);
    cout << "Checking existence of deleted item: "
         << ((search(bstRoot, 20)) ? "Still Exists!" : "Successfully Deleted.") << endl;

    // 清理资源
    destroyTree(bstRoot);

    return 0;
}