二叉树和二叉搜索树（Binary Search Tree, BST）是极为重要的树结构，广泛应用于数据的存储与检索。通过不同的遍历方式和操作方法，二叉树可以用于解决许多复杂的问题，尤其是二叉搜索树的高效查找、插入与删除操作，使其成为了构建自平衡树和数据库索引的基础。本文将详细讲解二叉树的遍历方法以及在二叉搜索树中的查找和删除操作。

二叉树基础

二叉树是一种树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以表示层次结构的数据，如表达式树、优先级队列等。

常见的二叉树类型包括：

• 满二叉树：每一个节点都有两个子节点。
• 完全二叉树：所有节点按层次排列，且最下层的节点尽可能地集中在左侧。
• 二叉搜索树（BST）：一种特殊的二叉树，满足每个节点的左子节点的值小于当前节点，而右子节点的值大于当前节点。

二叉树的遍历方法

二叉树的遍历是指按照某种顺序访问树中的所有节点。根据遍历顺序的不同，主要有四种常见的遍历方式：

1. 前序遍历（Preorder Traversal）

前序遍历按照 "根 -> 左 -> 右" 的顺序进行。首先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

实现代码（递归版）

function preorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];

    function traverse(node: TreeNode | null) {
        if (!node) return;
        result.push(node.value); // 访问根节点
        traverse(node.left); // 递归遍历左子树
        traverse(node.right); // 递归遍历右子树
    }

    traverse(root);
    return result;
}

2. 中序遍历（Inorder Traversal）

中序遍历按照 "左 -> 根 -> 右" 的顺序进行。首先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

实现代码（递归版）

function inorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];

    function traverse(node: TreeNode | null) {
        if (!node) return;
        traverse(node.left); // 递归遍历左子树
        result.push(node.value); // 访问根节点
        traverse(node.right); // 递归遍历右子树
    }

    traverse(root);
    return result;
}

3. 后序遍历（Postorder Traversal）

后序遍历按照 "左 -> 右 -> 根" 的顺序进行。首先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

实现代码（递归版）

function postorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];

    function traverse(node: TreeNode | null) {
        if (!node) return;
        traverse(node.left); // 递归遍历左子树
        traverse(node.right); // 递归遍历右子树
        result.push(node.value); // 访问根节点
    }

    traverse(root);
    return result;
}

4. 层序遍历（Level Order Traversal）

层序遍历按层次逐层访问二叉树的节点，依赖队列数据结构，从根节点开始，依次访问每一层的所有节点。

实现代码

function levelOrderTraversal(root: TreeNode | null): number[][] {
    if (!root) return [];

    const result: number[][] = [];
    const queue: (TreeNode | null)[] = [root];

    while (queue.length > 0) {
        const level: number[] = [];
        const size = queue.length;

        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            if (node) {
                level.push(node.value);
                if (node.left) queue.push(node.left);
                if (node.right) queue.push(node.right);
            }
        }

        result.push(level);
    }

    return result;
}

二叉搜索树（BST）的查找操作

二叉搜索树的一个显著特点是其有序性，即对于每个节点，左子树的所有节点值小于当前节点，右子树的所有节点值大于当前节点。这一性质使得查找操作可以高效地通过逐层缩小范围来实现。

查找操作

在 BST 中查找某个值时，可以从根节点开始，通过比较当前节点的值与目标值来决定是向左子树还是右子树继续搜索。

实现代码

function searchBST(root: TreeNode | null, target: number): TreeNode | null {
    if (!root || root.value === target) return root;

    if (target < root.value) {
        return searchBST(root.left, target); // 目标值小，查找左子树
    } else {
        return searchBST(root.right, target); // 目标值大，查找右子树
    }
}

二叉搜索树的插入操作

插入操作是指将一个新值插入到 BST 中，使得插入后的树仍保持二叉搜索树的性质。插入时，同样从根节点开始，逐层比较值的大小，找到合适的位置插入节点。

实现代码

function insertIntoBST(root: TreeNode | null, value: number): TreeNode {
    if (!root) return new TreeNode(value);

    if (value < root.value) {
        root.left = insertIntoBST(root.left, value); // 插入左子树
    } else {
        root.right = insertIntoBST(root.right, value); // 插入右子树
    }

    return root;
}

二叉搜索树的删除操作

删除操作是二叉搜索树中较为复杂的操作。根据待删除节点的不同情况，有三种主要情况需要处理：

1. 节点为叶子节点：直接删除。
2. 节点有一个子节点：删除节点并让子节点接替该位置。
3. 节点有两个子节点：找到右子树中的最小节点（或左子树中的最大节点）来替换该节点，然后删除该节点。

实现代码

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    if (!root) return null;

    if (key < root.value) {
        root.left = deleteNode(root.left, key); // 在左子树中删除
    } else if (key > root.value) {
        root.right = deleteNode(root.right, key); // 在右子树中删除
    } else {
        // 找到要删除的节点
        if (!root.left) return root.right; // 没有左子节点
        if (!root.right) return root.left; // 没有右子节点

        // 节点有两个子节点，找到右子树的最小节点
        let minNode = getMin(root.right);
        root.value = minNode!.value;
        root.right = deleteNode(root.right, minNode!.value); // 删除右子树中的最小节点
    }

    return root;
}

function getMin(node: TreeNode): TreeNode {
    while (node.left) node = node.left;
    return node;
}