二叉树遍历与二叉搜索树的Java实现

二叉树遍历

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

// 前序遍历：根 → 左 → 右
void preorder(TreeNode node) {
    if (node == null) return;
    visit(node);
    preorder(node.left);
    preorder(node.right);
}

// 前序遍历（非递归）
void preorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node == null) continue;
        visit(node);
        stack.push(node.right);  // 先右后左（栈LIFO）
        stack.push(node.left);
    }
}

// 中序遍历：左 → 根 → 右
void inorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {       // 一路向左
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        visit(cur);
        cur = cur.right;
    }
}

// 后序遍历：左 → 右 → 根
void postorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode lastVisited = null, cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.peek();
        if (cur.right == null || cur.right == lastVisited) {
            visit(stack.pop());
            lastVisited = cur;
            cur = null;
        } else {
            cur = cur.right;
        }
    }
}

二叉搜索树操作

class BST {
    TreeNode root;
    
    TreeNode search(int val) {
        TreeNode cur = root;
        while (cur != null && cur.val != val) {
            cur = val < cur.val ? cur.left : cur.right;
        }
        return cur;
    }
    
    TreeNode insert(TreeNode node, int val) {
        if (node == null) return new TreeNode(val);
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        return node;
    }
    
    TreeNode delete(TreeNode node, int val) {
        if (node == null) return null;
        
        if (val < node.val) {
            node.left = delete(node.left, val);
        } else if (val > node.val) {
            node.right = delete(node.right, val);
        } else {
            // 情况1：叶子节点
            if (node.left == null && node.right == null) return null;
            // 情况2：只有一个子节点
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;
            // 情况3：有两个子节点 → 找右子树最小值（或左子树最大值）
            TreeNode min = findMin(node.right);
            node.val = min.val;
            node.right = delete(node.right, min.val);
        }
        return node;
    }
}

应用场景

• 二叉树：表达式树、Huffman编码树、决策树
• BST：快速查找/插入/删除（平均O(log n)，最坏O(n)）
• 自平衡BST（AVL/红黑树）：TreeMap/TreeSet/数据库索引实现