思想：前序（根左右），中序（左根右），后序（左右根）
前序非递归遍历：
首先判断根是否为空，将根节点入栈
1.若栈为空，则退出循环
2.将栈顶元素弹出，访问弹出的节点
3.若弹出的节点的右孩子不为空则将右孩子入栈
4.若弹出的节点的左孩子不为空则将左孩子入栈
5.返回1
后序遍历非递归：
前序：根->左->右
后序：左->右->根
可以把后序当作：根->右->左，然后再反转一下即可
中序遍历非递归：
根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：
对于任一结点P，
1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束。
树结构
/**
* Copyright(C) 2019 Hangzhou Differsoft Co., Ltd. All rights reserved.
*
*/
package com.java.offer.tree; /**
* @since 2019年2月15日 上午9:23:17
* @author xuchao
*
* 树节点
*/
public class TreeNode<T> { public T val;
public TreeNode<T> left;
public TreeNode<T> right; public TreeNode(T val) {
this.val = val;
this.left = null;
this.right = null;
}
}
程序：
/**
* Copyright(C) 2019 Hangzhou Differsoft Co., Ltd. All rights reserved.
*
*/
package com.java.offer.tree; import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack; /**
* @since 2019年2月15日 上午9:28:07
* @author xuchao
*
* 二叉树的遍历：
* 前序（根左右），中序（左根右），后序（左右根），层序
*/
public class TraversalOfBinaryTree { // 前序递归
public static List<Integer> preorderRecursively(TreeNode<Integer> node){
List<Integer> list = new ArrayList<>();
if (node == null) {
return list;
}
list.add(node.val);
list.addAll(preorderRecursively(node.left));
list.addAll(preorderRecursively(node.right));
return list;
}
// 中序递归
public static List<Integer> inorderRecursively(TreeNode<Integer> node){
List<Integer> list = new ArrayList<>();
if (node == null) {
return list;
}
list.addAll(inorderRecursively(node.left));
list.add(node.val);
list.addAll(inorderRecursively(node.right));
return list;
} // 后序递归
public static List<Integer> postorderRecursively(TreeNode<Integer> node){
List<Integer> list = new ArrayList<>();
if (node == null) {
return list;
}
list.addAll(postorderRecursively(node.left));
list.addAll(postorderRecursively(node.right));
list.add(node.val);
return list;
} // 前序非递归
public static List<Integer> preorderIteratively(TreeNode<Integer> node) {
Stack<TreeNode<Integer>> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
if (node == null) {
return list;
}
stack.push(node);
while (!stack.isEmpty()) {
node = stack.pop();
list.add(node.val);
if(node.right!=null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return list;
} // 中序非递归
public static List<Integer> inorderIteratively(TreeNode<Integer> node) {
Stack<TreeNode<Integer>> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
TreeNode<Integer> cur = node;
if (node == null) {
return list;
}
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
}else {
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
} // 后序非递归
public static List<Integer> postorderIteratively(TreeNode<Integer> node) {
Stack<TreeNode<Integer>> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
if (node == null) {
return list;
}
stack.push(node);
while(!stack.isEmpty()) {
node = stack.pop();
list.add(node.val);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
Collections.reverse(list);
return list;
} // 层次遍历
public static List<Integer> levelorder(TreeNode<Integer> node) {
Queue<TreeNode<Integer>> queue = new LinkedList<>();
List<Integer> list = new ArrayList<>();
if (node == null) {
return list;
}
queue.add(node);
while (!queue.isEmpty()) {
node = queue.remove();
list.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if(node.right!=null) {
queue.add(node.right);
}
}
return list;
} // 1
// 2 3
// 4 5 // pre:1-2-4-3-5 in:2-4-1-5-3 post:4-2-5-3-1 level:1-2-3-4-5
public static void main(String[] args) {
TreeNode<Integer> node = new TreeNode<Integer>(1);
node.left = new TreeNode<Integer>(2);
node.right = new TreeNode<Integer>(3);
node.left.right = new TreeNode<Integer>(4);
node.right.left = new TreeNode<Integer>(5); // 前中后遍历递归
System.out.println(preorderRecursively(node).toString());
System.out.println(inorderRecursively(node).toString());
System.out.println(postorderRecursively(node).toString()); System.out.println("");
// 前中后遍历非递归
System.out.println(preorderIteratively(node).toString());
System.out.println(inorderIteratively(node).toString());
System.out.println(postorderIteratively(node).toString()); // 层次遍历
System.out.println(levelorder(node).toString());
}
}