二叉排序树

一、二叉排序树的定义

性质：
- 对于每个节点 N，满足：
  1. 若左子树不为空，则左子树中所有节点的值均小于 N 的值。
  2. 若右子树不为空，则右子树中所有节点的值均大于 N 的值。
- 左右子树本身也必须是二叉排序树。
特点：
- 中序遍历的结果是一个升序排列的序列。
- 数据存储动态且可扩展，适合频繁的插入、删除和查找操作。

二、二叉排序树的基本操作

1. 定义节点结构

二叉排序树的节点通常包括数据值和左右子树指针：

struct TreeNode {
    int value;               // 节点的值
    TreeNode* left;          // 指向左子树的指针
    TreeNode* right;         // 指向右子树的指针

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

2. 插入节点

插入节点时递归定位插入位置，保持二叉排序树的性质：

TreeNode* insert(TreeNode* root, int value) {
    if (!root) return new TreeNode(value);  // 空节点，创建新节点
    if (value < root->value)
        root->left = insert(root->left, value);  // 插入左子树
    else if (value > root->value)
        root->right = insert(root->right, value); // 插入右子树
    return root;
}

3. 查找节点

从根节点开始，递归或迭代查找目标值：

TreeNode* search(TreeNode* root, int value) {
    if (!root || root->value == value) return root;  // 找到目标节点或遍历结束
    if (value < root->value)
        return search(root->left, value);  // 在左子树中查找
    return search(root->right, value);     // 在右子树中查找
}

4. 删除节点

删除节点需分三种情况处理：

节点为叶子节点：直接删除。
节点有一个子节点：用子节点替代。
节点有两个子节点：用右子树的最小节点[待删除结点的中序直接后]（或左子树的最大节点[待删除结点的中序直接前驱]）替代，然后删除该节点。
待删除结点左右子树都存在，有两种处理方式:
(1) 用其右子树中序遍历第一个结点(关键码最小)填补其位置，再来处理这个结点的删除问题
(2) 用其左子树中序遍历最后一个结点(关键码最大)填补其位置，再来处理这个结点的删除问题这两种方式中用来填补的结点要么是叶子结点，要么只有左子树或右子树，即是前三种情形

TreeNode* findMin(TreeNode* root) {
    while (root && root->left) root = root->left;  // 找到最小值节点
    return root;
}

TreeNode* deleteNode(TreeNode* root, int value) {
    if (!root) return nullptr;
    if (value < root->value)
        root->left = deleteNode(root->left, value);  // 删除左子树节点
    else if (value > root->value)
        root->right = deleteNode(root->right, value);  // 删除右子树节点
    else {
        // 节点有两个子节点
        if (root->left && root->right) {
            TreeNode* temp = findMin(root->right);  // 找到右子树最小节点
            root->value = temp->value;  // 替换节点值
            root->right = deleteNode(root->right, temp->value);  // 删除最小节点
        } else {
            // 节点只有一个子节点或没有子节点
            TreeNode* temp = root->left ? root->left : root->right;
            delete root;
            return temp;
        }
    }
    return root;
}

5. 遍历

中序遍历（从小到大输出）：

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

前序遍历：

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

后序遍历：

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

三、二叉排序树的完整实现

以下是一个完整的 C++ 示例代码，包含插入、查找、删除和遍历功能：

#include <iostream>
using namespace std;

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

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

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

TreeNode* search(TreeNode* root, int value) {
    if (!root || root->value == value) return root;
    if (value < root->value)
        return search(root->left, value);
    return search(root->right, value);
}

TreeNode* findMin(TreeNode* root) {
    while (root && root->left) root = root->left;
    return root;
}

TreeNode* deleteNode(TreeNode* root, int value) {
    if (!root) return nullptr;
    if (value < root->value)
        root->left = deleteNode(root->left, value);
    else if (value > root->value)
        root->right = deleteNode(root->right, value);
    else {
        if (!root->left) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        if (!root->right) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        TreeNode* temp = findMin(root->right);
        root->value = temp->value;
        root->right = deleteNode(root->right, temp->value);
    }
    return root;
}

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

int main() {
    TreeNode* root = nullptr;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);

    cout << "Inorder Traversal: ";
    inorderTraversal(root);
    cout << endl;

    cout << "Searching for 40: " << (search(root, 40) ? "Found" : "Not Found") << endl;

    root = deleteNode(root, 50);
    cout << "After deleting 50, Inorder Traversal: ";
    inorderTraversal(root);
    cout << endl;

    return 0;
}