Java堆栈如何存储二叉树？

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

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

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

1. 替代递归：避免递归导致的栈溢出（StackOverflowError）
2. 控制访问顺序：按前序/中序/后序遍历节点
3. 空间效率：空间复杂度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);
    }
}

执行流程：

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

中序遍历（左→根→右）

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; // 转向右子树
    }
}

执行流程：

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

后序遍历（左→右→根）

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 递归的对比

应用场景

1. 深度优先搜索（DFS）：路径查找、回溯算法
2. 表达式树求值：通过后序遍历栈计算
3. 序列化二叉树：前序+中序遍历栈重建二叉树
4. 非递归算法优化：避免递归层级限制（如Java默认栈深度~10,000）

关键提示：
实际存储二叉树时，堆栈仅作为临时容器，若需持久化存储，应结合前序/中序遍历序列化到文件或数据库。

引用说明

1. 算法设计参考《算法导论》深度优先遍历非递归实现
2. Java Stack类文档：Oracle官方Java 17 Specifications
3. 二叉树遍历理论：Stanford CS106B课程资料

通过堆栈实现二叉树遍历，开发者能精准控制内存使用，避免递归缺陷,尤其适合处理超大规模树结构数据。