Java实现二叉树的前序、中序、后序、层序遍历（非递归方法）

  在上一篇博客中，实现了Java中二叉树的四种遍历方式的递归实现，接下来，在此实现Java中非递归实现二叉树的前序、中序、后序、层序遍历，在非递归实现中，借助了栈来帮助实现遍历。前序和中序比较类似，也简单一些，但是后序遍历需要两个栈来进行辅助，稍微复杂一些，层序遍历中借助了一个队列来进行实现。

  同样是那棵二叉树

• 前序遍历：4 2 1 3 6 5 7 8 10

• 中序遍历：1 2 3 4 5 6 7 8 10

• 后序遍历：1 3 2 5 10 8 7 6 4

• 层序遍历：4 2 6 1 3 5 7 8 10

  import java.util.LinkedList; import java.util.Queue; import java.util.Stack;

  public class Tree<AnyType extends Comparable<? super AnyType>> { private static class BinaryNode { BinaryNode(AnyType theElement) { this(theElement, null, null); } BinaryNode(AnyType theElement, BinaryNode lt, BinaryNode rt) { element = theElement; left = lt; right = rt; } AnyType element; BinaryNode left; BinaryNode right; } private BinaryNode root; public void insert(AnyType x) { root = insert(x, root); } public boolean isEmpty() { return root == null; } private BinaryNode insert(AnyType x, BinaryNode t) { if(t == null) { return new BinaryNode<>(x, null, null); } int compareResult = x.compareTo(t.element); if(compareResult < 0) { t.left = insert(x, t.left); } else if(compareResult > 0) { t.right = insert(x, t.right); } else { ; } return t; } /** * 前序遍历 * 递归 / public void preOrder(BinaryNode Node) { if (Node != null) { System.out.print(Node.element + " "); preOrder(Node.left); preOrder(Node.right); } } /* * 中序遍历 * 递归 / public void midOrder(BinaryNode Node) { if (Node != null) { midOrder(Node.left); System.out.print(Node.element + " "); midOrder(Node.right); } } /* * 后序遍历 * 递归 / public void posOrder(BinaryNode Node) { if (Node != null) { posOrder(Node.left); posOrder(Node.right); System.out.print(Node.element + " "); } } / * 层序遍历 * 递归 / public void levelOrder(BinaryNode Node) { if (Node == null) { return; } int depth = depth(Node); for (int i = 1; i <= depth; i++) { levelOrder(Node, i); } } private void levelOrder(BinaryNode Node, int level) { if (Node == null || level < 1) { return; } if (level == 1) { System.out.print(Node.element + " "); return; } // 左子树 levelOrder(Node.left, level - 1); // 右子树 levelOrder(Node.right, level - 1); } public int depth(BinaryNode Node) { if (Node == null) { return 0; } int l = depth(Node.left); int r = depth(Node.right); if (l > r) { return l + 1; } else { return r + 1; } } /* * 前序遍历 * 非递归 / public void preOrder1(BinaryNode Node) { Stack stack = new Stack<>(); while(Node != null || !stack.empty()) { while(Node != null) { System.out.print(Node.element + " "); stack.push(Node); Node = Node.left; } if(!stack.empty()) { Node = stack.pop(); Node = Node.right; } } } /* * 中序遍历 * 非递归 / public void midOrder1(BinaryNode Node) { Stack stack = new Stack<>(); while(Node != null || !stack.empty()) { while (Node != null) { stack.push(Node); Node = Node.left; } if(!stack.empty()) { Node = stack.pop(); System.out.print(Node.element + " "); Node = Node.right; } } } /* * 后序遍历 * 非递归 / public void posOrder1(BinaryNode Node) { Stack stack1 = new Stack<>(); Stack stack2 = new Stack<>(); int i = 1; while(Node != null || !stack1.empty()) { while (Node != null) { stack1.push(Node); stack2.push(0); Node = Node.left; } while(!stack1.empty() && stack2.peek() == i) { stack2.pop(); System.out.print(stack1.pop().element + " "); } if(!stack1.empty()) { stack2.pop(); stack2.push(1); Node = stack1.peek(); Node = Node.right; } } } / * 层序遍历 * 非递归 */ public void levelOrder1(BinaryNode Node) { if (Node == null) { return; } BinaryNode binaryNode; Queue queue = new LinkedList<>(); queue.add(Node); while (queue.size() != 0) { binaryNode = queue.poll(); System.out.print(binaryNode.element + " "); if (binaryNode.left != null) { queue.offer(binaryNode.left); } if (binaryNode.right != null) { queue.offer(binaryNode.right); } } } public static void main( String[] args ) { int[] input = {4, 2, 6, 1, 3, 5, 7, 8, 10}; Tree tree = new Tree<>(); for(int i = 0; i < input.length; i++) { tree.insert(input[i]); } System.out.print("递归前序遍历 ："); tree.preOrder(tree.root); System.out.print("\n非递归前序遍历："); tree.preOrder1(tree.root); System.out.print("\n递归中序遍历 ："); tree.midOrder(tree.root); System.out.print("\n非递归中序遍历 ："); tree.midOrder1(tree.root); System.out.print("\n递归后序遍历 ："); tree.posOrder(tree.root); System.out.print("\n非递归后序遍历 ："); tree.posOrder1(tree.root); System.out.print("\n递归层序遍历："); tree.levelOrder(tree.root); System.out.print("\n非递归层序遍历 ："); tree.levelOrder1(tree.root); } }