|
t; 0) {
136 // 把当前节点和其右侧子结点推入栈
137 while (node != null) {
138 stack.push(node);
139 temp.push(node);
140 node = node.right;
141 }
142 // 处理栈顶节点的左子树
143 if (stack.size() > 0) {
144 node = stack.pop();
145 node = node.left;
146 }
147 }
148 while (temp.size() > 0) {
149 node = temp.pop();
150 visit(node);
151 }
152 }
153
154 /** 二叉树广度优先遍历——层序遍历 */
155 public static void layerTraversal(BinaryTreeNode root) {
156 Queue<BinaryTreeNode> queue = new LinkedList<>();
157
158 if (root != null) {
159 queue.add(root);
160 while (!queue.isEmpty()) {
161 BinaryTreeNode currentNode = queue.poll();
162 visit(currentNode);
163 if (currentNode.left != null) {
164 queue.add(currentNode.left);
165 }
166
167 if (currentNode.right != null) {
168 queue.add(currentNode.right);
169 }
170
171 }
172 }
173 }
174
175 public static void main(String[] args) {
176
177 // 构造二叉树
178 // 1
179 // / \
180 // 2 3
181 // / / \
182 // 4 5 7
183 // \ /
184 // 6 8
185 BinaryTreeNode root = new BinaryTreeNode(1);
186 BinaryTreeNode node2 = new BinaryTreeNode(2);
187 BinaryTreeNode node3 = new BinaryTreeNode(3);
188 BinaryTreeNode node4 = new BinaryTreeNode(4);
189 BinaryTreeNode node5 = new BinaryTreeNode(5);
190 BinaryTreeNode node6 = new BinaryTreeNode(6);
191 BinaryTreeNode node7 = new BinaryTreeNode(7);
192 BinaryTreeNode node8 = new BinaryTreeNode(8);
193
194 root.left = node2;
195 root.right = node3;
196 node2.left = node4;
197 node3.left = node5;
198 node3.right = node7;
199 node5.right = node6;
200 node7.left = node8;
201 System.out.println("二叉树先序遍历");
202 preOrder(root);
203 System.out.println("二叉树先序遍历非递归");
204 iterativePreorder(root);
205 System.out.println("二叉树中序遍历");
206 inOrder(root);
207 System.out.println("二叉树中序遍历非递归");
208 iterativeInOrder(root);
209 System.out.println("二叉树后序遍历");
210 postOrder(root);
211 System.out.println("二叉树单栈非递归后序遍历");
212 iterativePostOrder(root);
213 System.out.println("二叉树双栈非递归后序遍历");
214 iterativePostOrderByTwoStacks(root);
215 System.out.println("二叉树层树序遍历");
216 layerTraversal(root);
217 }
218 }
|