数据结构——二叉树的非递归的前序遍历&&中序遍历&&后序非递归遍历

Han.miracle

发布于 2025-12-23 09:57:12

660

文章被收录于专栏：Java核心技术图谱：原理·对比·避坑Java核心技术图谱：原理·对比·避坑

二叉树的非递归前序遍历

首先创建一个栈，用于存储节点。如果根节点为空，直接返回。
定义一个当前节点cur，初始化为根节点。
外层循环的条件是 “当前节点不为空或者栈不为空”：

内层循环会不断将当前节点的左子节点入栈，直到当前节点的左子节点为空（这一步是为了找到最左的节点）。
弹出栈顶节点（这个节点就是当前要访问的 “根” 节点），输出它的值。
然后将当前节点指向该节点的右子节点，继续外层循环，处理右子树的中序遍历

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

// 二叉树节点定义
class TreeNode {
    int val;          // 节点值
    TreeNode left;    // 左子节点
    TreeNode right;   // 右子节点
    TreeNode(int x) { val = x; }  // 构造方法
}

public class PreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
      
        // 空树直接返回空列表
        if (root == null) {
            return result;
        }
        
        // 初始化栈，用于存储待访问的节点
        Stack<TreeNode> stack = new Stack<>();
        // 根节点先入栈
        stack.push(root);
        TreeNode cur = root;
        // 栈不为空时，循环处理节点
        while (!stack.isEmpty()|| cur !=null) {
        while(cur != null){
        System.out.print(top.val + " ");
            stack.push(cur);
            cur = cur.left;
          }
          //栈里的最后一个先出来，所以就是先把这个值给top,即使他是null也给他，因为上面会检查他的是不是null，如果是的话再弹出一个值
            TreeNode top = stack.pop();
            
            cur = top.right;
        }
        
       
    }
}

还有一种方法：节点入栈时就打印，而不是弹出时打印

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

// 二叉树节点定义
class TreeNode {
    int val;        
    TreeNode left;    
    TreeNode right;   
    TreeNode(int x) { val = x; } 
}

public class PreorderTraversal {
 public List<Integer> traverse(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    result.add(root.val); // 入栈时打印

    while (!stack.isEmpty()) {
     // 弹出栈顶节点，准备处理其子树
        TreeNode node = stack.pop(); 

        // 先压左子树，再压右子树（因为入栈时就打印）
        if (node.left != null) {
            stack.push(node.left);
            result.add(node.left.val); 
        }
        if (node.right != null) {
            stack.push(node.right);
            result.add(node.right.val); 
        }
    }
    return result;
}
}

还有一种方法就是同时把左右两边的值都压进去，但是如果存起来的时候，因为栈的特性是先进后出，后进先出 核心就是：每次循环处理完当前 “根节点” 后，会将右、左子树依次入栈，而由于栈 “后进先出” 的特性，左子树会在下一次循环中被优先弹出并加入结果

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

// 二叉树节点定义
class TreeNode {
    int val;          // 节点值
    TreeNode left;    // 左子节点
    TreeNode right;   // 右子节点
    TreeNode(int x) { val = x; }  // 构造方法
}

public class PreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 存储遍历结果的列表
        List<Integer> result = new ArrayList<>();
        // 空树直接返回空列表
        if (root == null) {
            return result;
        }
        
        // 初始化栈，用于存储待访问的节点
        Stack<TreeNode> stack = new Stack<>();
        // 根节点先入栈
        stack.push(root);
        
        // 栈不为空时，循环处理节点
        while (!stack.isEmpty()) {
            // 1. 弹出栈顶节点（视为当前“根节点”）
            TreeNode node = stack.pop();
            // 2. 访问该节点（加入结果集）
            result.add(node.val);
            
            // 3. 右子节点先入栈（后处理）
            if (node.right != null) {
                stack.push(node.right);
            }
            // 4. 左子节点后入栈（先处理）
            if (node.left != null) {
                stack.push(node.left);
            }
            //每次循环处理完当前 “根节点” 后，会将右、左子树依次入栈，而由于栈 “后进先出” 的特性，左子树会在下一次循环中被优先弹出并加入结果
        }
        
        return result;
    }
}

中序非递归遍历

//左边一直迭代，然后迭代到为空的时候跟前序非递归遍历是一样的
//就是根节点的打印位置变了
public class PreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
      
        // 空树直接返回空列表
        if (root == null) {
            return result;
        }
        
        // 初始化栈，用于存储待访问的节点
        Stack<TreeNode> stack = new Stack<>();
        // 根节点先入栈
        stack.push(root);
        TreeNode cur = root;
        // 栈不为空时，循环处理节点
        while (!stack.isEmpty()|| cur !=null) {
        while(cur != null){
            stack.push(cur);
            //前序再往下找的时候遇到的节点直接打印了
            cur = cur.left;
          }
         
            TreeNode top = stack.pop();
            //左边的遍历打印完成了，直接找到上一个节点然后进行打印根节点没然后再去走右边的子树
            System.out.print(top.val + " ");
            cur = top.right;
        }

后续非递归遍历

按着思路我

TreeNode cur = root;
while (cur != null || !stack.empty()) {
    while (cur != null) {
        stack.push(cur);
        cur = cur.left;
    }
    top = stack.peek();
    if (top.right == null) {
        sout(top.val);
        stack.pop();
    } else {
        cur = top.right;
    }
}

乍一看这个代码没有问题，

 TreeNode cur = root;
while (cur != null || !stack.empty()) {
    while (cur != null) {
        stack.push(cur);
        cur = cur.left;
    }
    top = stack.peek();
    if (top.right == null) {
        sout(top.val);
        stack.pop();
    } else {
        cur = top.right;
    }
}

在这一块代码就不对劲了， cur = K的时候， k的左边的子树为null,但是栈不为空所以接着往下走

  if (top.right == null) {
        sout(top.val);
        stack.pop();

到这里，K的右边也为null，所以k打印并且弹出这时候cur = null 了

   top = stack.peek();
    if (top.right == null) {
        sout(top.val);
        stack.pop();
    } else {
        cur = top.right;
    }

走这里重新peek()取出来D,此时可以发现进入循环了，这是这个代码的问题，我们需要及逆行修改一下啊

public void postOrderNor(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return;
    }
    TreeNode prev = null;
    TreeNode cur = root;
    while (cur != null || !stack.empty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode top = stack.peek();
        //若栈顶节点的右子树为空，说明该节点的左右子树都已处理完毕
        //top.right == prev：若栈顶节点的右子树不为空，但右子树的根节点是上一个刚访问过的节点（prev），说明右子树已处理完毕，可访问当前节点
        if (top.right == null || top.right == prev) {
            System.out.print(top.val + " ");
            stack.pop();
            prev = top;
           //prev指针记录上一个访问的节点，巧妙解决了后序遍历中 "左→右→根" 的访问顺序
        } else {
            cur = top.right;
        }
    }
}

prev的作用：如果右子树为空（top.right == null），直接可以访问当前节点；如果右子树不为空，但 prev 指向右子树的根节点（top.right == prev），说明右子树已经遍历完成，此时可以访问当前节点；否则，需要先去遍历右子树（将 cur 指向右子树，继续入栈处理）。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-29，如有侵权请联系 cloudcommunity@tencent.com 删除

存储