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<AnyType> { BinaryNode(AnyType theElement) { this(theElement, null, null); }
1 BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt) 2 { 3 element = theElement; 4 left = lt; 5 right = rt; 6 } 7 8 AnyType element; 9 BinaryNode<AnyType> left; 10 BinaryNode<AnyType> right; 11} 12 13private BinaryNode<AnyType> root; 14 15public void insert(AnyType x) 16{ 17 root = insert(x, root); 18} 19 20public boolean isEmpty() 21{ 22 return root == null; 23} 24 25private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) 26{ 27 if(t == null) 28 { 29 return new BinaryNode<>(x, null, null); 30 } 31 32 int compareResult = x.compareTo(t.element); 33 34 if(compareResult < 0) 35 { 36 t.left = insert(x, t.left); 37 } 38 else if(compareResult > 0) 39 { 40 t.right = insert(x, t.right); 41 } 42 else 43 { 44 ; 45 } 46 47 return t; 48} 49 50/** 51 * 前序遍历 52 * 递归 53 */ 54public void preOrder(BinaryNode<AnyType> Node) 55{ 56 if (Node != null) 57 { 58 System.out.print(Node.element + " "); 59 preOrder(Node.left); 60 preOrder(Node.right); 61 } 62} 63 64/** 65 * 中序遍历 66 * 递归 67 */ 68public void midOrder(BinaryNode<AnyType> Node) 69{ 70 if (Node != null) 71 { 72 midOrder(Node.left); 73 System.out.print(Node.element + " "); 74 midOrder(Node.right); 75 } 76} 77 78/** 79 * 后序遍历 80 * 递归 81 */ 82public void posOrder(BinaryNode<AnyType> Node) 83{ 84 if (Node != null) 85 { 86 posOrder(Node.left); 87 posOrder(Node.right); 88 System.out.print(Node.element + " "); 89 } 90} 91 92/* 93 * 层序遍历 94 * 递归 95 */ 96public void levelOrder(BinaryNode<AnyType> Node) { 97 if (Node == null) { 98 return; 99 } 100 101 int depth = depth(Node); 102 103 for (int i = 1; i <= depth; i++) { 104 levelOrder(Node, i); 105 } 106} 107 108private void levelOrder(BinaryNode<AnyType> Node, int level) { 109 if (Node == null || level < 1) { 110 return; 111 } 112 113 if (level == 1) { 114 System.out.print(Node.element + " "); 115 return; 116 } 117 118 // 左子树 119 levelOrder(Node.left, level - 1); 120 121 // 右子树 122 levelOrder(Node.right, level - 1); 123} 124 125public int depth(BinaryNode<AnyType> Node) { 126 if (Node == null) { 127 return 0; 128 } 129 130 int l = depth(Node.left); 131 int r = depth(Node.right); 132 if (l > r) { 133 return l + 1; 134 } else { 135 return r + 1; 136 } 137} 138 139/** 140 * 前序遍历 141 * 非递归 142 */ 143public void preOrder1(BinaryNode<AnyType> Node) 144{ 145 Stack<BinaryNode> stack = new Stack<>(); 146 while(Node != null || !stack.empty()) 147 { 148 while(Node != null) 149 { 150 System.out.print(Node.element + " "); 151 stack.push(Node); 152 Node = Node.left; 153 } 154 if(!stack.empty()) 155 { 156 Node = stack.pop(); 157 Node = Node.right; 158 } 159 } 160} 161 162/** 163 * 中序遍历 164 * 非递归 165 */ 166public void midOrder1(BinaryNode<AnyType> Node) 167{ 168 Stack<BinaryNode> stack = new Stack<>(); 169 while(Node != null || !stack.empty()) 170 { 171 while (Node != null) 172 { 173 stack.push(Node); 174 Node = Node.left; 175 } 176 if(!stack.empty()) 177 { 178 Node = stack.pop(); 179 System.out.print(Node.element + " "); 180 Node = Node.right; 181 } 182 } 183} 184 185/** 186 * 后序遍历 187 * 非递归 188 */ 189public void posOrder1(BinaryNode<AnyType> Node) 190{ 191 Stack<BinaryNode> stack1 = new Stack<>(); 192 Stack<Integer> stack2 = new Stack<>(); 193 int i = 1; 194 while(Node != null || !stack1.empty()) 195 { 196 while (Node != null) 197 { 198 stack1.push(Node); 199 stack2.push(0); 200 Node = Node.left; 201 } 202 203 while(!stack1.empty() && stack2.peek() == i) 204 { 205 stack2.pop(); 206 System.out.print(stack1.pop().element + " "); 207 } 208 209 if(!stack1.empty()) 210 { 211 stack2.pop(); 212 stack2.push(1); 213 Node = stack1.peek(); 214 Node = Node.right; 215 } 216 } 217} 218 219/* 220 * 层序遍历 221 * 非递归 222 */ 223public void levelOrder1(BinaryNode<AnyType> Node) { 224 if (Node == null) { 225 return; 226 } 227 228 BinaryNode<AnyType> binaryNode; 229 Queue<BinaryNode> queue = new LinkedList<>(); 230 queue.add(Node); 231 232 while (queue.size() != 0) { 233 binaryNode = queue.poll(); 234 235 System.out.print(binaryNode.element + " "); 236 237 if (binaryNode.left != null) { 238 queue.offer(binaryNode.left); 239 } 240 if (binaryNode.right != null) { 241 queue.offer(binaryNode.right); 242 } 243 } 244} 245 246public static void main( String[] args ) 247{ 248 int[] input = {4, 2, 6, 1, 3, 5, 7, 8, 10}; 249 Tree<Integer> tree = new Tree<>(); 250 for(int i = 0; i < input.length; i++) 251 { 252 tree.insert(input[i]); 253 } 254 System.out.print("递归前序遍历 ："); 255 tree.preOrder(tree.root); 256 System.out.print("\n非递归前序遍历："); 257 tree.preOrder1(tree.root); 258 System.out.print("\n递归中序遍历 ："); 259 tree.midOrder(tree.root); 260 System.out.print("\n非递归中序遍历 ："); 261 tree.midOrder1(tree.root); 262 System.out.print("\n递归后序遍历 ："); 263 tree.posOrder(tree.root); 264 System.out.print("\n非递归后序遍历 ："); 265 tree.posOrder1(tree.root); 266 System.out.print("\n递归层序遍历："); 267 tree.levelOrder(tree.root); 268 System.out.print("\n非递归层序遍历 ："); 269 tree.levelOrder1(tree.root); 270}}