实现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
/** * 前序遍历——非迭代 */ public void nonRecOrder(TreeNode root) { if (root == null) { return; } Stack stack = new Stack<>(); stack.push(root); // 拿出元素 while (stack.size() > 0) { TreeNode node = stack.pop(); System.out.println("非递归前序遍历节点：" + node.data); if (node.rightChild != null) { stack.push(node.rightChild); } if (node.leftChild != null) { stack.push(node.leftChild); } // 继续拿出元素进行遍历，这时拿的应该是左边的 } }
/** * 中序遍历——非迭代 * * @author Administrator * */ public void nonMidOrder(TreeNode node) { if (node == null) { return; } Stack stack = new Stack<>(); while (node != null || stack.size() > 0) { while (node != null) { stack.push(node); node = node.leftChild; } // 所有的左子节点压栈后，开始出栈 // 拿到栈顶的节点 node = stack.pop(); System.out.println("非递归中序遍历节点：" + node.data); node = node.rightChild; } }
/** * 后序遍历——非迭代 * * @author Administrator * */ public void nonPostOrder(TreeNode node) { if (node == null) { return; } Stack stack = new Stack<>(); TreeNode lastVisitNode = null; while (node != null) { stack.push(node); node = node.leftChild; } // 先从最后一个左子节点开始判断 while (stack.size() > 0) { // 判断当前节点是否有右子节点，并且该右子节点没有被访问过 node = stack.pop(); if (node.rightChild != null && node.rightChild != lastVisitNode) { // 说明有右子节点，该根节点还需要再被用到，所以压回栈 stack.push(node); node = node.rightChild; while (node != null) { stack.push(node); node = node.leftChild; } } else { // 说明当前的节点没右子节点（左子节点也没有） System.out.println("非递归后序遍历节点：" + node.data); // 访问过后，代表该节点被访问过 lastVisitNode = node; } } }
// 层次遍历 public void levelOrder(TreeNode node) { if (node == null) { return; } LinkedList list = new LinkedList<>(); list.addLast(node); while (list.size() > 0) { // 取出队头元素 node = list.removeFirst(); System.out.println("层次遍历：" + node.data); if (node.leftChild != null) { list.addLast(node.leftChild); } if (node.rightChild != null) { list.addLast(node.rightChild); } } }