import java.util.ArrayDeque; public class NonRecuDfs { public static ArrayDeque<TreeNode> preArr = new ArrayDeque<>(); public static ArrayDeque<TreeNode> inArr = new ArrayDeque<>(); public static ArrayDeque<TreeNode> afterArr = new ArrayDeque<>(); public static void preOrder(TreeNode root){ while(!preArr.isEmpty() || root!=null){ if(root!=null){ System.out.print(root.val+" "); preArr.push(root); root = root.left; }else{ TreeNode t = preArr.pop(); root = t.right; } } } public static void inOrder(TreeNode root){ while(!inArr.isEmpty() || root!=null){ if(root!=null){ inArr.push(root); root = root.left; }else{ TreeNode t = inArr.pop(); System.out.print(t.val+" "); root = t.right; } } } public static void afterOrder(TreeNode root){ TreeNode pre = null; while(!afterArr.isEmpty() || root!=null){ while(root!=null){ afterArr.push(root); root = root.left; } root = afterArr.pop();//通过栈可以确定,当前出栈元素的左子树都已经访问过了,剩下右子树需要靠pre来确定是否访问过 if(root.right==null || root.right==pre){ //右子树为空或者已被访问 System.out.print(root.val+" "); pre = root; root = null;//设为空避免下次的while循环 }else { afterArr.push(root); root = root.right; } } } public static void main(String[] args) { TreeNode treeNode = new TreeNode(1); TreeNode treeNode1 = new TreeNode(2); TreeNode treeNode2 = new TreeNode(3); TreeNode treeNode3 = new TreeNode(4); TreeNode treeNode4 = new TreeNode(5); TreeNode treeNode5 = new TreeNode(6); treeNode.left = treeNode1; treeNode.right = treeNode2; treeNode1.left = treeNode3; treeNode1.right = treeNode4; treeNode2.left = treeNode5; preOrder(treeNode); System.out.println(); inOrder(treeNode); System.out.println(); afterOrder(treeNode); } } class TreeNode { int val; TreeNode left = null; TreeNode right = null; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }