Java实现二叉树的先序遍历含递归，非递归，Morris

标题：Java实现二叉树的先序遍历含递归，非递归，Morris

/** * 我的第一个二叉树 * @author dell * */ public class TestMyTreeB { /** * 测试遍历二叉树的先序遍历【先输出节点的值】 * @param p */ public void preorder(IntNode p) { if(p == null) { return ; }else { System.out.print(p.val + " "); this.preorder(p.left); this.preorder(p.right); } } /** * 执行用时：13 ms, 在所有 Java 提交中击败了46.70% 的用户 内存消耗：37 MB, 在所有 Java 提交中击败了63.10% 的用户 * @param p */ public void preorder02(IntNode p) { Deque<IntNode> s = new LinkedList<>(); if(p == null) { return ; } s.push(p); while(!s.isEmpty()) { System.out.print(s.peek().val + " "); while(s.peek().left != null) { //一直遍历最左边 IntNode node = s.peek().left; System.out.print(node.val + " "); s.push(node); } IntNode node = s.peek().right; //获取右节点的值 s.pop(); //删除 while(!s.isEmpty() && node == null) { //右边为null node = s.peek().right; s.pop(); } if(node != null){ s.push(node); } } } /** * 书上的先序遍历，非递归 * * 执行用时：11 ms, 在所有 Java 提交中击败了46.53% 的用户 内存消耗：36.9 MB, 在所有 Java 提交中击败了71.88% 的用户 * @param p */ public void preorder03(IntNode p) { Deque<IntNode> s = new LinkedList<>(); if(p == null) { return ; } s.push(p); while(!s.isEmpty()) { System.out.print(s.peek().val + " "); IntNode node = s.pop(); if(node.right != null) { s.push(node.right); } if(node.left != null) { s.push(node.left); } } } @Test public void test02() { IntNode p1 = new IntNode('a'); IntNode p2 = new IntNode('b'); IntNode p3 = new IntNode('c'); IntNode p4 = new IntNode('d'); IntNode p5 = new IntNode('e'); IntNode p6 = new IntNode('f'); IntNode p7 = new IntNode('g'); IntNode p8 = new IntNode('h'); IntNode p9 = new IntNode('i'); IntNode p10 = new IntNode('j'); IntNode p11 = new IntNode('k'); p1.left = p2; p1.right = p3; p2.left = p4; p2.right = p5; p4.right = p6; p5.left = p7; p5.right = p8; p3.left = p9; p3.right = p10; p10.right =p11; System.out.println("递归的先序遍历"); this.preorder(p1); System.out.println(); System.out.println("测试非递归先序遍历"); this.preorder02(p1); System.out.println(); System.out.println("测试非递归先序遍历 【树上的】"); this.preorder03(p1); System.out.println(); } }