当前位置：首页 > 后端开发 > 正文

Java堆栈如何存储二叉树？

admin
后端开发
2025-06-18
3349

在Java中，堆栈存储二叉树主要用于非递归遍历（如先序、中序、后序），通过堆栈的LIFO特性暂存节点：根节点先入栈，循环中弹出节点处理，再按特定顺序压入子节点（如先序需先右后左），从而模拟递归调用栈实现深度优先遍历。

在Java中，堆栈（Stack）通过非递归的深度优先遍历（DFS）存储二叉树数据，核心思路是利用栈的LIFO（后进先出）特性模拟递归过程,以下是详细实现方法及原理：

堆栈存储二叉树的底层逻辑

堆栈本身不直接“存储”二叉树结构，而是通过辅助遍历将节点按特定顺序存入栈中,实现以下操作：

Java堆栈如何存储二叉树？第1张

替代递归：避免递归导致的栈溢出（StackOverflowError）
控制访问顺序：按前序/中序/后序遍历节点
空间效率：空间复杂度O(h)（h为树高），优于递归的O(n)

堆栈遍历二叉树的三种方式（附Java代码）

前序遍历（根→左→右）

public void preOrderStack(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " "); // 访问根节点
        // 右子节点先入栈（保证左子节点先出栈）
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

执行流程：

根节点入栈 → 弹出并访问
右子节点入栈 → 左子节点入栈
重复弹出栈顶节点（左子优先）

中序遍历（左→根→右）

public void inOrderStack(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        // 深入左子树到底部
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        System.out.print(curr.val + " "); // 访问节点
        curr = curr.right; // 转向右子树
    }
}

执行流程：

从根节点向左深入，所有左子节点入栈
弹出栈顶（最左节点）并访问
处理该节点的右子树

后序遍历（左→右→根）

public void postOrderStack(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    Stack<Integer> result = new Stack<>(); // 辅助栈存储结果
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.push(node.val); // 根节点值存入结果栈
        // 左子节点先入栈（保证右子节点先进入结果栈）
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    // 反向输出结果栈（实现左右根→根右左的逆序）
    while (!result.isEmpty()) {
        System.out.print(result.pop() + " ");
    }
}

关键点：
利用辅助栈反转访问顺序（根→右→左 → 逆序输出为左→右→根）

堆栈 vs 递归的对比

特性	堆栈实现	递归实现
空间复杂度	O(h) (h=树高度)	O(n) (递归深度)
栈溢出风险	无	树过高时可能发生
代码可控性	高（显式控制栈操作）	低（依赖系统调用栈）
适用场景	超深二叉树、迭代逻辑	代码简洁性要求高