二叉树先序,中序,后序遍历都是相对于父节点(有孩子的节点),或者单一节点而言的。左右二孩节点相对位置不变。此节点如果先遍历则为先序,在中间则为中序,在最后则为后续。
图片来源于百度!
import java.util.Stack; public class PreMidAfter { public static void main(String[] args) { TreeNode[] treeNodes = new TreeNode[10]; for (int i = 0; i < 10; i++) { treeNodes[i] = new TreeNode(i); } for (int i = 0; i <= 16/2-1; i++) { if(i*2+1 < 10) treeNodes[i].left = treeNodes[i*2+1]; if(i*2+2 < 10) treeNodes[i].right = treeNodes[i*2+2]; } TreeNode header = treeNodes[0]; //pre(header); //mid(header); after(header); } /** * 先序遍历 * 访问当前元素,并压入栈中一次遍历左孩节点,当左孩为空,则找寻其右孩节点 * 按照上面循环,遍历每个左右分支 * @param root */ public static void pre(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); while (root!=null || !stack.isEmpty()) { while (root!=null) { System.out.print(root.val+"\t"); stack.push(root); root = root.left; } if(stack!=null) { root = stack.pop(); root = root.right; } } } /** * 与先序遍历类似 * @param root */ public static void mid(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); while (root!=null || !stack.isEmpty()) { while (root!=null) { stack.push(root); root = root.left; } if(stack!=null) { root = stack.pop(); System.out.print(root.val+"\t"); root = root.right; } } } /** * 当从右孩节点返回到父节点,则可以输出值 * @param root */ public static void after(TreeNode root) { int left=1,right = 2; Stack<TreeNode> stack = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); while (root!=null || !stack.isEmpty()) { //压入所有左节点 while (root!=null) { stack.push(root); stack2.push(left); root = root.left; } while (!stack.isEmpty() && stack2.peek() == right) { stack2.pop(); System.out.print(stack.pop().val+" "); } if(!stack.isEmpty() && stack2.peek() == left) { stack2.pop(); stack2.push(right); root = stack.peek().right; } } } }