12.二叉排序树基本操作\n\n实现二叉排序树的下面基本操作，并在main函数中调用要求:\n\n1)构建二叉排序树\n\n2)二叉排序树的遍历输出\n\n3)在二叉排序树中查找给定值\n\n4)在二叉排序树中插入新结点

这个问题是关于二叉排序树的基本操作。

1) 构建二叉排序树，就是从空树开始，逐个插入结点的过程。插入结点时，按照二叉排序树的规则，将结点插入到正确的位置。

2) 遍历输出二叉排序树的历史记录，可以通过中序遍历二叉排序树，得到有序的记录序列。

3) 在二叉排序树中查找给定值，可以使用二叉查找的方法，从根节点开始，逐个比较要查找的值和结点的值，找到目标结点或者找到空节点为止。

4) 插入新结点，按照二叉排序的规则，在找到合适位置的空节点处插入新结点。

这些操作可以在main函数中调用来完成二叉排序树的建立、遍历、查找和插入。

相关问题

根据二叉排序树的抽象数据类型的定义，使用二叉链表实现一个二叉排序树，并编写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;
}

编写二叉排序树的操作函数，并在main主函数中依次调用基本操作函数。①建立二叉排序树。②二叉排序树的插入。③二叉排序树的查找。④树的遍历。注意什么

好的，这是一个关于二叉排序树的问题。我会尽力回答你的问题。

首先，二叉排序树是一种特殊的二叉树，它的每个节点都包含一个关键字，且满足左子树的关键字都小于根节点的关键字，右子树的关键字都大于根节点的关键字。二叉排序树具有以下性质：

1. 对于二叉排序树中的任意节点，它的左子树中的所有节点的关键字都小于该节点的关键字，右子树中的所有节点的关键字都大于该节点的关键字；

2. 对于二叉排序树中的任意节点，它的左子树和右子树也是二叉排序树。

接下来，我们来分别实现建立二叉排序树、二叉排序树的插入、二叉排序树的查找和树的遍历。

建立二叉排序树的函数实现：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* createBST(vector<int>& nums) {
    if (nums.empty()) {
        return NULL;
    }
    TreeNode* root = new TreeNode(nums[0]);
    for (int i = 1; i < nums.size(); i++) {
        TreeNode* cur = root;
        while (cur) {
            if (nums[i] < cur->val) {
                if (cur->left) {
                    cur = cur->left;
                } else {
                    cur->left = new TreeNode(nums[i]);
                    break;
                }
            } else {
                if (cur->right) {
                    cur = cur->right;
                } else {
                    cur->right = new TreeNode(nums[i]);
                    break;
                }
            }
        }
    }
    return root;
}

二叉排序树的插入函数实现：

TreeNode* insertBST(TreeNode* root, int val) {
    if (!root) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insertBST(root->left, val);
    } else if (val > root->val) {
        root->right = insertBST(root->right, val);
    }
    return root;
}

二叉排序树的查找函数实现：

bool searchBST(TreeNode* root, int val) {
    if (!root) {
        return false;
    }
    if (root->val == val) {
        return true;
    } else if (root->val > val) {
        return searchBST(root->left, val);
    } else {
        return searchBST(root->right, val);
    }
}

树的遍历函数实现：

void inorderTraversal(TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        cout << root->val << " ";
        inorderTraversal(root->right);
    }
}

void preorderTraversal(TreeNode* root) {
    if (root) {
        cout << root->val << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

void postorderTraversal(TreeNode* root) {
    if (root) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        cout << root->val << " ";
    }
}

在 main 函数中调用这些函数：

int main() {
    vector<int> nums = {5, 3, 7, 2, 4, 6, 8};
    TreeNode* root = createBST(nums);
    inorderTraversal(root);
    cout << endl;
    preorderTraversal(root);
    cout << endl;
    postorderTraversal(root);
    cout << endl;
    insertBST(root, 1);
    inorderTraversal(root);
    cout << endl;
    insertBST(root, 9);
    inorderTraversal(root);
    cout << endl;
    cout << searchBST(root, 4) << endl;
    cout << searchBST(root, 10) << endl;
    return 0;
}

需要注意以下几点：

1. 建立二叉排序树时，需要注意处理 nums 为空的情况。

2. 插入元素时，需要递归寻找插入位置。

3. 查找时，需要递归查找。

4. 遍历时，需要注意遍历顺序。

以上是关于二叉排序树的基本操作函数的实现和使用方法，希望能对你有所帮助。