7-3 数据结构实验四 二叉排序树

二叉排序树（Binary Search Tree，简称BST）是一种特殊的二叉树，它具有以下性质：
1. 左子树上的所有节点的值都小于根节点的值。
2. 右子树上的所有节点的值都大于根节点的值。
3. 左右子树也分别为二叉排序树。

二叉排序树主要用于实现动态查找，可以高效地插入、删除和查找元素。下面是二叉排序树的实现步骤：

1. 建立二叉排序树：
- 如果树为空，将新节点作为根节点。
- 如果树不为空，从根节点开始，比较新节点的值与当前节点的值的大小关系：
- 如果新节点的值小于当前节点的值，将新节点插入到当前节点的左子树中。
- 如果新节点的值大于当前节点的值，将新节点插入到当前节点的右子树中。
- 如果新节点的值等于当前节点的值，不进行插入操作。

2. 遍历二叉排序树：
- 前序遍历：先访问根节点，然后递归地遍历左子树和右子树。
- 中序遍历：先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。
- 后序遍历：先递归地遍历左子树和右子树，最后访问根节点。

3. 删除节点：
- 如果要删除的节点是叶子节点，直接删除即可。
- 如果要删除的节点只有一个子节点，将子节点替换为要删除的节点。
- 如果要删除的节点有两个子节点，可以选择用其前驱节点或后继节点替换。

4. 查找并记录访问次数：
- 从根节点开始，比较要查找的值与当前节点的值的大小关系：
- 如果要查找的值小于当前节点的值，继续在左子树中查找。
- 如果要查找的值大于当前节点的值，继续在右子树中查找。
- 如果要查找的值等于当前节点的值，找到了目标节点，并记录访问次数。

5. 利用快速排序的思想将负数排在正数前：
- 在建立二叉排序树时，可以将负数插入到左子树中，将正数插入到右子树中，这样就可以实现负数排在正数前的效果。

以下是一个二叉排序树的示例代码：

#include <iostream>

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

void insert(TreeNode*& root, int value) {
    if (root == nullptr) {
        root = new TreeNode;
        root->value = value;
        root->left = nullptr;
        root->right = nullptr;
    } else if (value < root->value) {
        insert(root->left, value);
    } else if (value > root->value) {
        insert(root->right, value);
    }
}

void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->value << " ";
        inorderTraversal(root->right);
    }
}

int main() {
    TreeNode* root = nullptr;

    // 插入节点
    insert(root, 5);
    insert(root, 3);
    insert(root, 7);
    insert(root, 2);
    insert(root, 4);
    insert(root, 6);
    insert(root, 8);

    // 中序遍历
    inorderTraversal(root); // 输出：2 3 4 5 6 7 8

    return 0;
}