二叉搜索树模板

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 查找
Node* search(Node *root, int key) {
    if (!root || root->val == key) return root;
    if (key < root->val) return search(root->left, key);
    return search(root->right, key);
}

// 插入
Node* insert(Node *root, int key) {
    if (!root) return new Node(key);
    if (key < root->val) root->left = insert(root->left, key);
    else if (key > root->val) root->right = insert(root->right, key);
    return root;
}

// 中序遍历（得到有序序列）
void inorder(Node *root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    Node *root = nullptr;
    int a[] = {5, 3, 7, 1, 4, 6, 8};
    for (int x : a) root = insert(root, x);
    inorder(root);  // 1 3 4 5 6 7 8
    return 0;
}

📖 要点说明

• BST 性质：左子树 < 根 < 右子树
• 中序遍历 BST 得到升序序列
• 查找/插入平均 O(log n)，最坏 O(n)

⚠️ 常见错误

• BST 退化成链（顺序插入时）
• 删除节点时子树处理复杂
• 重复值的处理方式不统一