Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/10.二叉排序树.md

10. 二叉排序树

概念

二叉排序树（Binary Search Tree, BST），也叫二叉查找树，是一棵满足以下性质的二叉树（假设结点值为整数，且不允许重复）：

• 若左子树非空，则左子树上所有结点值都小于根结点的值；
• 若右子树非空，则右子树上所有结点值都大于根结点的值；
• 左、右子树本身也分别是二叉排序树（递归定义）。

由定义可推出一个重要结论：对二叉排序树进行中序遍历（左-根-右），得到的一定是一个递增的有序序列。因此 BST 天然支持"边插入边保持有序"，查找、插入、删除都基于值的大小比较，每次比较就能排除一半的子树。

为什么平均复杂度是 O(log n)？ 在理想情况下，树的形态比较均衡（接近完全二叉树），树高约为 log₂n，而每次查找/插入/删除每下降一层只做 O(1) 的比较和指针操作，所以平均时间是 O(log n)。

为什么可能退化成链表？ 如果按有序序列（如 1,2,3,...,n）依次插入，则每个新结点总是成为上一个结点的右孩子，树退化成一条"斜树/链"，树高变成 n。此时查找、插入、删除的最坏时间复杂度退化到 O(n)，与线性表无异。这也是后续引入平衡二叉树（AVL）的动机。

适用场景：动态数据的查找/插入/删除（符号表、字典）、排序（中序遍历）、作为 AVL 树和红黑树的基础。二叉排序树常用来实现查找效率较好的动态查找表。

核心操作

• 查找：从根开始，key 小于当前结点值则往左走，大于则往右走，相等则命中；走到空结点则未找到。可用递归或非递归（迭代）实现。
• 插入：先查找，若 key 已存在则插入失败；否则走到空位置，把新结点挂上（作为叶结点）。
• 删除：分三种情况——
  1. 删除叶子结点：直接删除，父结点对应指针置空；
  2. 删除只有一棵子树的结点：用它的孩子顶替它；
  3. 删除有两棵子树的结点：用其前驱（左子树中的最大结点）或后继（右子树中的最小结点）的值覆盖它，然后删除那个前驱/后继结点（前驱/后继至多只有一棵子树，转回情况 1 或 2）。
• 创建：从一个空树开始，依次插入各元素，或用数组逐个插入构造。
• 中序遍历：左-根-右递归输出，得到有序序列。

复杂度分析

操作	平均时间复杂度	最坏时间复杂度	空间复杂度
查找	O(log n)	O(n)	递归 O(log n)/O(n)，迭代 O(1)
插入	O(log n)	O(n)	O(1)
删除	O(log n)	O(n)	递归 O(log n)/O(n)
中序遍历	O(n)	O(n)	递归 O(log n)/O(n)

为什么：平均情形树高约 log₂n，每层操作 O(1)，故平均 O(log n)；最坏情形（如有序插入形成斜树）树高为 n，故退化为 O(n)。中序遍历要访问所有 n 个结点，恒为 O(n)。

语言实现

下面是 4 种语言的完整可运行实现，均演示同一组操作：插入若干元素、中序遍历输出、查找某个值、删除某个值后再中序遍历。

C

#include <stdio.h>
#include <stdlib.h>

// 二叉排序树结点
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

// 创建新结点
Node *createNode(int data) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 递归查找：找到返回结点指针，否则返回 NULL
Node *search(Node *root, int key) {
    if (root == NULL || root->data == key)
        return root;
    if (key < root->data)
        return search(root->left, key);
    else
        return search(root->right, key);
}

// 非递归查找
Node *searchIter(Node *root, int key) {
    while (root != NULL && root->data != key) {
        if (key < root->data)
            root = root->left;
        else
            root = root->right;
    }
    return root;
}

// 插入：返回新的树根
Node *insert(Node *root, int data) {
    if (root == NULL)
        return createNode(data);
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    // data == root->data 视为重复，不插入
    return root;
}

// 找到子树中的最小结点（一直往左走）
Node *findMin(Node *root) {
    while (root->left != NULL)
        root = root->left;
    return root;
}

// 删除：返回新的树根
Node *deleteNode(Node *root, int key) {
    if (root == NULL)
        return NULL;
    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        // 情况1：叶子结点（或只有一边为空的处理）
        if (root->left == NULL) {          // 无左子树：用右孩子顶替
            Node *temp = root->right;
            free(root);
            return temp;
        }
        if (root->right == NULL) {         // 无右子树：用左孩子顶替
            Node *temp = root->left;
            free(root);
            return temp;
        }
        // 情况3：有两棵子树，用后继（右子树最小值）覆盖
        Node *succ = findMin(root->right);
        root->data = succ->data;
        root->right = deleteNode(root->right, succ->data);
    }
    return root;
}

// 中序遍历：得到有序序列
void inorder(Node *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int main() {
    Node *root = NULL;
    int a[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++)
        root = insert(root, a[i]);

    printf("中序遍历: ");
    inorder(root);
    printf("\n");

    // 查找
    Node *found = search(root, 40);
    printf("查找 40: %s\n", found ? "找到" : "未找到");
    found = searchIter(root, 99);
    printf("查找 99: %s\n", found ? "找到" : "未找到");

    // 删除叶结点 20
    root = deleteNode(root, 20);
    printf("删除 20 后中序遍历: ");
    inorder(root);
    printf("\n");

    // 删除单子树结点 30
    root = deleteNode(root, 30);
    printf("删除 30 后中序遍历: ");
    inorder(root);
    printf("\n");

    // 删除双子树结点 50（用后继覆盖）
    root = deleteNode(root, 50);
    printf("删除 50 后中序遍历: ");
    inorder(root);
    printf("\n");

    return 0;
}

C++

#include <iostream>
using namespace std;

// 二叉排序树结点
struct Node {
    int data;
    Node *left, *right;
    Node(int d) : data(d), left(nullptr), right(nullptr) {}
};

// 递归查找
Node *search(Node *root, int key) {
    if (root == nullptr || root->data == key)
        return root;
    return key < root->data ? search(root->left, key) : search(root->right, key);
}

// 非递归查找
Node *searchIter(Node *root, int key) {
    while (root && root->data != key) {
        root = key < root->data ? root->left : root->right;
    }
    return root;
}

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

// 子树最小值（后继）
Node *findMin(Node *root) {
    while (root->left)
        root = root->left;
    return root;
}

// 删除
Node *deleteNode(Node *root, int key) {
    if (root == nullptr)
        return nullptr;
    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        if (root->left == nullptr) {
            Node *temp = root->right;
            delete root;
            return temp;
        }
        if (root->right == nullptr) {
            Node *temp = root->left;
            delete root;
            return temp;
        }
        Node *succ = findMin(root->right);
        root->data = succ->data;
        root->right = deleteNode(root->right, succ->data);
    }
    return root;
}

// 中序遍历
void inorder(Node *root) {
    if (!root) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main() {
    Node *root = nullptr;
    for (int x : {50, 30, 70, 20, 40, 60, 80})
        root = insert(root, x);

    cout << "中序遍历: ";
    inorder(root);
    cout << endl;

    cout << "查找 40: " << (search(root, 40) ? "找到" : "未找到") << endl;
    cout << "查找 99: " << (searchIter(root, 99) ? "找到" : "未找到") << endl;

    root = deleteNode(root, 20);
    cout << "删除 20 后: ";
    inorder(root);
    cout << endl;

    root = deleteNode(root, 30);
    cout << "删除 30 后: ";
    inorder(root);
    cout << endl;

    root = deleteNode(root, 50);
    cout << "删除 50 后: ";
    inorder(root);
    cout << endl;

    return 0;
}

Java

public class BST {

    // 结点
    static class Node {
        int data;
        Node left, right;
        Node(int d) { data = d; }
    }

    private Node root;

    // 递归查找
    public Node search(int key) { return search(root, key); }
    private Node search(Node n, int key) {
        if (n == null || n.data == key) return n;
        return key < n.data ? search(n.left, key) : search(n.right, key);
    }

    // 非递归查找
    public Node searchIter(int key) {
        Node n = root;
        while (n != null && n.data != key)
            n = key < n.data ? n.left : n.right;
        return n;
    }

    // 插入
    public void insert(int data) { root = insert(root, data); }
    private Node insert(Node n, int data) {
        if (n == null) return new Node(data);
        if (data < n.data) n.left = insert(n.left, data);
        else if (data > n.data) n.right = insert(n.right, data);
        return n;
    }

    // 子树最小值
    private Node findMin(Node n) {
        while (n.left != null) n = n.left;
        return n;
    }

    // 删除
    public void delete(int key) { root = delete(root, key); }
    private Node delete(Node n, int key) {
        if (n == null) return null;
        if (key < n.data) n.left = delete(n.left, key);
        else if (key > n.data) n.right = delete(n.right, key);
        else {
            if (n.left == null) return n.right;
            if (n.right == null) return n.left;
            Node succ = findMin(n.right);
            n.data = succ.data;
            n.right = delete(n.right, succ.data);
        }
        return n;
    }

    // 中序遍历
    public void inorder() { inorder(root); System.out.println(); }
    private void inorder(Node n) {
        if (n == null) return;
        inorder(n.left);
        System.out.print(n.data + " ");
        inorder(n.right);
    }

    public static void main(String[] args) {
        BST bst = new BST();
        int[] a = {50, 30, 70, 20, 40, 60, 80};
        for (int x : a) bst.insert(x);

        System.out.print("中序遍历: ");
        bst.inorder();

        System.out.println("查找 40: " + (bst.search(40) != null ? "找到" : "未找到"));
        System.out.println("查找 99: " + (bst.searchIter(99) != null ? "找到" : "未找到"));

        bst.delete(20);
        System.out.print("删除 20 后: ");
        bst.inorder();

        bst.delete(30);
        System.out.print("删除 30 后: ");
        bst.inorder();

        bst.delete(50);
        System.out.print("删除 50 后: ");
        bst.inorder();
    }
}

Python

class Node:
    """二叉排序树结点"""
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BST:
    def __init__(self):
        self.root = None

    def search(self, key):
        """递归查找"""
        return self._search(self.root, key)

    def _search(self, n, key):
        if n is None or n.data == key:
            return n
        return self._search(n.left, key) if key < n.data else self._search(n.right, key)

    def search_iter(self, key):
        """非递归查找"""
        n = self.root
        while n is not None and n.data != key:
            n = n.left if key < n.data else n.right
        return n

    def insert(self, data):
        self.root = self._insert(self.root, data)

    def _insert(self, n, data):
        if n is None:
            return Node(data)
        if data < n.data:
            n.left = self._insert(n.left, data)
        elif data > n.data:
            n.right = self._insert(n.right, data)
        return n

    def _find_min(self, n):
        while n.left is not None:
            n = n.left
        return n

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, n, key):
        if n is None:
            return None
        if key < n.data:
            n.left = self._delete(n.left, key)
        elif key > n.data:
            n.right = self._delete(n.right, key)
        else:
            if n.left is None:
                return n.right
            if n.right is None:
                return n.left
            succ = self._find_min(n.right)   # 用后继覆盖
            n.data = succ.data
            n.right = self._delete(n.right, succ.data)
        return n

    def inorder(self):
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, n, result):
        if n is None:
            return
        self._inorder(n.left, result)
        result.append(n.data)
        self._inorder(n.right, result)


if __name__ == "__main__":
    bst = BST()
    for x in [50, 30, 70, 20, 40, 60, 80]:
        bst.insert(x)

    print("中序遍历:", bst.inorder())
    print("查找 40:", "找到" if bst.search(40) else "未找到")
    print("查找 99:", "找到" if bst.search_iter(99) else "未找到")

    bst.delete(20)
    print("删除 20 后:", bst.inorder())
    bst.delete(30)
    print("删除 30 后:", bst.inorder())
    bst.delete(50)
    print("删除 50 后:", bst.inorder())