每日算法 — 使用java实现二叉搜索树：递归操作与Morris遍历优化

引言

二叉搜索树（Binary Search Tree，BST）是一种经典的有序数据结构，它支持高效的查找、插入和删除操作。在理想情况下，这些操作的时间复杂度均为 O(log n)。本文将用 Java 完整实现二叉搜索树的核心操作，并深入讲解 Morris 中序遍历算法——一种不需要借助递归或额外栈空间、仅用 O(1) 额外空间即可完成树遍历的精妙技巧。

二叉搜索树的定义与性质

二叉搜索树满足以下性质：
– 任意节点的左子树中所有节点的值均小于该节点的值
– 任意节点的右子树中所有节点的值均大于该节点的值
– 左右子树本身也必须是二叉搜索树
– 树中不存在值相等的节点

基于以上性质，BST 的中序遍历结果是一个严格递增的有序序列。

节点定义

/**
 * 二叉搜索树节点类
 * 每个节点包含：数据值、左子节点引用、右子节点引用
 */
class TreeNode {
    int val;           // 节点存储的数值
    TreeNode left;     // 左子节点
    TreeNode right;    // 右子节点

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

二叉搜索树的核心操作

查找操作

查找是 BST 最基本的操作。从根节点出发，根据目标值与当前节点值的大小关系决定向左或向右遍历，直到找到目标值或遍历到空节点。

/**
 * 在二叉搜索树中查找指定值的节点
 * 时间复杂度：平均 O(log n)，最坏 O(n)（树退化为链表时）
 *
 * @param root 当前子树的根节点
 * @param target 要查找的目标值
 * @return 找到的节点，不存在则返回 null
 */
public TreeNode search(TreeNode root, int target) {
    TreeNode current = root;
    while (current != null) {
        if (target == current.val) {
            return current;  // 找到目标值
        } else if (target < current.val) {
            current = current.left;   // 目标值更小，向左子树搜索
        } else {
            current = current.right;  // 目标值更大，向右子树搜索
        }
    }
    return null;  // 遍历到空节点，说明目标值不存在
}

插入操作

插入操作首先找到合适的空位置，然后将新节点挂载到该位置。新节点总是作为叶子节点插入。

/**
 * 向二叉搜索树中插入一个新值
 * 若值已存在则不进行任何操作（保证树中无重复值）
 * 时间复杂度：平均 O(log n)，最坏 O(n)
 *
 * @param root 当前子树的根节点
 * @param val 要插入的值
 * @return 插入后的根节点
 */
public TreeNode insert(TreeNode root, int val) {
    // 找到空位置，创建新节点
    if (root == null) {
        return new TreeNode(val);
    }

    if (val < root.val) {
        // 新值小于当前节点值，插入左子树
        root.left = insert(root.left, val);
    } else if (val > root.val) {
        // 新值大于当前节点值，插入右子树
        root.right = insert(root.right, val);
    }
    // 若 val == root.val，不做任何操作（不插入重复值）

    return root;
}

删除操作

删除操作是 BST 中最复杂的操作，需要分三种情况处理：

删除叶子节点：直接删除即可
删除只有一个子节点的节点：用其子节点替代自身
删除有两个子节点的节点：找到右子树的最小值节点（或左子树的最大值节点）替代自身，然后删除那个最小值节点

/**
 * 从二叉搜索树中删除指定值的节点
 * 时间复杂度：平均 O(log n)，最坏 O(n)
 *
 * @param root 当前子树的根节点
 * @param val 要删除的值
 * @return 删除后的根节点
 */
public TreeNode delete(TreeNode root, int val) {
    if (root == null) {
        return null;  // 树为空或找不到目标值
    }

    if (val < root.val) {
        // 目标值在左子树中
        root.left = delete(root.left, val);
    } else if (val > root.val) {
        // 目标值在右子树中
        root.right = delete(root.right, val);
    } else {
        // 找到要删除的节点
        // 情况1：叶子节点或只有一个子节点
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }

        // 情况2：有两个子节点
        // 找到右子树中的最小值节点（后继节点）
        TreeNode successor = findMin(root.right);
        // 用后继节点的值替换当前节点的值
        root.val = successor.val;
        // 在右子树中删除后继节点
        root.right = delete(root.right, successor.val);
    }

    return root;
}

/**
 * 查找以 root 为根的子树中的最小值节点
 * 即不断向左遍历直到左子节点为空
 */
private TreeNode findMin(TreeNode root) {
    while (root.left != null) {
        root = root.left;
    }
    return root;
}

Morris 中序遍历：O(1) 空间的树遍历

核心思想

传统的中序遍历需要借助递归栈或显式栈，空间复杂度为 O(h)（h 为树高）。Morris 遍历的核心思想是：

对于当前节点，找到其在中序遍历中的前驱节点（左子树的最右节点）
如果前驱节点的右子节点为空，将其右子节点指向当前节点（建立临时线索），然后移动到左子节点
如果前驱节点的右子节点已经指向当前节点，说明左子树已经遍历完毕，恢复树的结构（断开线索），访问当前节点，然后移动到右子节点

算法实现

import java.util.ArrayList;
import java.util.List;

/**
 * Morris 中序遍历算法
 * 时间复杂度：O(n) — 每个节点被访问常数次
 * 空间复杂度：O(1) — 仅使用几个指针变量
 */
public List<Integer> morrisInorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode current = root;

    while (current != null) {
        if (current.left == null) {
            // 当前节点没有左子树，直接访问当前节点，然后转向右子树
            result.add(current.val);
            current = current.right;
        } else {
            // 找到当前节点左子树中的最右节点（前驱节点）
            TreeNode predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }

            if (predecessor.right == null) {
                // 第一次访问前驱节点，建立线索
                predecessor.right = current;
                current = current.left;
            } else {
                // 第二次访问前驱节点，说明左子树已遍历完毕
                // 断开线索，恢复树的原始结构
                predecessor.right = null;
                result.add(current.val);  // 访问当前节点
                current = current.right;  // 转向右子树
            }
        }
    }

    return result;
}

Morris 遍历的执行流程图解

以如下二叉搜索树为例：

Morris 中序遍历的执行过程：
1. 从 4 开始，左子树存在，找到前驱节点 3，建立 3->4 的线索，移动到 2
2. 从 2 开始，左子树存在，找到前驱节点 1，建立 1->2 的线索，移动到 1
3. 1 没有左子树，访问 1，移动到 2（通过 right 指针）
4. 回到 2，前驱节点 1 的 right 已指向 2，断开线索，访问 2，移动到 3
5. 3 没有左子树，访问 3，移动到 4（通过线索）
6. 回到 4，前驱节点 3 的 right 已指向 4，断开线索，访问 4，移动到 6
7. 以此类推，最终遍历结果：1, 2, 3, 4, 5, 6, 7

完整的二叉搜索树类

public class BinarySearchTree {
    private TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    // 查找操作
    public boolean contains(int val) {
        return search(root, val) != null;
    }

    // 插入操作（对外接口）
    public void add(int val) {
        root = insert(root, val);
    }

    // 删除操作（对外接口）
    public void remove(int val) {
        root = delete(root, val);
    }

    // Morris 中序遍历（对外接口）
    public List<Integer> inorderTraversal() {
        return morrisInorder(root);
    }

    // 传统的递归中序遍历（用于对比验证）
    public List<Integer> recursiveInorder() {
        List<Integer> result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }

    private void inorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorderHelper(node.left, result);
        result.add(node.val);
        inorderHelper(node.right, result);
    }

    // 以下是前文实现的私有方法
    private TreeNode search(TreeNode root, int target) { /* ... */ return null; }
    private TreeNode insert(TreeNode root, int val) { /* ... */ return null; }
    private TreeNode delete(TreeNode root, int val) { /* ... */ return null; }
    private TreeNode findMin(TreeNode root) { /* ... */ return null; }
    private List<Integer> morrisInorder(TreeNode root) { /* ... */ return null; }

    // 主方法：测试验证
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // 插入测试数据
        int[] values = {4, 2, 6, 1, 3, 5, 7};
        for (int val : values) {
            bst.add(val);
        }

        System.out.println("中序遍历结果（Morris）: " + bst.inorderTraversal());
        System.out.println("中序遍历结果（递归）: " + bst.recursiveInorder());

        // 删除测试
        bst.remove(2);
        System.out.println("删除 2 后（Morris）: " + bst.inorderTraversal());

        // 查找测试
        System.out.println("包含 5? " + bst.contains(5));
        System.out.println("包含 2? " + bst.contains(2));
    }
}

复杂度分析

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

最坏情况发生在树退化为链表时，此时树高为 n。为避免这种情况，实际应用中常使用 AVL 树或红黑树等自平衡二叉搜索树。

总结

二叉搜索树是算法学习中不可或缺的基础数据结构。本文完整实现了 BST 的查找、插入和删除操作，并重点介绍了 Morris 中序遍历这一空间优化技巧。Morris 遍历通过巧妙地在遍历过程中建立和断开临时线索，将传统需要 O(h) 栈空间的树遍历优化到了 O(1) 额外空间，是理解”空间换时间”与”时间换空间”平衡关系的绝佳案例。掌握 BST 及其遍历优化，将为后续学习 AVL 树、红黑树等高级数据结构打下坚实基础。

Tagged with: Java Morris遍历二叉搜索树二叉树