不使用递归也可以实现二叉树的前序中序后序遍历,二叉树前序中序后序java

递归实现

前言

二叉树的非递归利用栈实现，栈的特性是先进后出，实现回溯

二叉树的节点定义 private static class TreeNode { int data; TreeNode leftChild; TreeNode rightChild; public TreeNode(int data) { this.data = data; } } 前序遍历

前序遍历的输出顺序是根节点 -> 左子树 -> 右子树

public static void preOrderTraveralWithStack (TreeNode node) { if (node == null) { return; } Stack stack = new Stack<>(); TreeNode treeNode = node; while (treeNode != null || !stack.isEmpty()) { while (treeNode != null) { System.out.print(treeNode.data + " "); stack.push(treeNode); treeNode = treeNode.leftChild; } if (!stack.isEmpty()) { treeNode = stack.pop(); treeNode = treeNode.rightChild; } } } 中序遍历

中序遍历的输出顺序是左子树 -> 根节点 -> 右子树

public static void inOrderTraveralWithStack (TreeNode node) { if (node == null) { return; } Stack stack = new Stack<>(); TreeNode treeNode = node; while (treeNode != null || !stack.isEmpty()) { while (treeNode != null) { stack.push(treeNode); treeNode = treeNode.leftChild; } if (!stack.isEmpty()) { treeNode = stack.pop(); System.out.print(treeNode.data + " "); treeNode = treeNode.rightChild; } } } 后序遍历

后序遍历的输出顺序是左子树 -> 右子树 -> 根节点

利用栈stack1回溯记录前一节点，如果有左子树先压入栈stack1，如果有右子树后压入栈stack2，栈stack2作为辅助栈存储根节点 -> 右子树 -> 左子树，输出时利用栈先进后出的特性，逆序输出变成后序遍历的顺序左子树 -> 右子树 -> 根节点

public static void postOrderTraveralWithStack (TreeNode node) { if (node == null) { return; } Stack stack1 = new Stack<>(); Stack stack2 = new Stack<>(); // 辅助栈 存储 根->右->左 TreeNode treeNode = node; stack1.push(treeNode); while (!stack1.isEmpty()) { treeNode = stack1.pop(); stack2.push(treeNode); if (treeNode.leftChild != null) { stack1.push(treeNode.leftChild); } if (treeNode.rightChild != null) { stack1.push(treeNode.rightChild); } } while (!stack2.isEmpty()) { System.out.print(stack2.pop().data + " "); } } 总结

大部分利用递归解决的问题，都可以利用栈解决，因为递归和栈都有回溯的特性