本文编写于 1954 天前，最后修改于 1505 天前，其中某些信息可能已经过时。
介绍
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。二叉树的遍历分为：前序遍历、中序遍历和后序遍历。
实现
public class BinaryTreeTraversal {
/**
* 二叉树结点类
* @param <T> 二叉树存储的数据对象类型
*/
private static class TreeNode<T> {
/** 节点存储的值 */
private T data;
/** 左孩子节点 */
private TreeNode<T> leftChild;
/** 右孩子节点 */
private TreeNode<T> rightChild;
/**
* 二叉树节点的构造方法
* @param data 节点存储的值
*/
TreeNode(T data) {
this.data = data;
}
}
/**
* 标记节点类，用于二叉树的后序遍历时作标记使用
* @param <T> 二叉树存储的数据对象类型
*/
private static class TagNode<T> {
/** 需要标记的节点 */
private TreeNode<T> treeNode;
/** 是否是第一次访问 */
private boolean isFirst;
}
/**
* 构建二叉树，用二叉树的前序遍历线性链表构建一颗二叉树
* @param list 二叉树的前序遍历线性链表
* @param <T> 二叉树存储的数据对象类型
* @return 构建后的二叉树根节点
*/
public static <T> TreeNode<T> createBinaryNode(LinkedList<T> list) {
if (list == null || list.isEmpty()) {
return null;
}
TreeNode<T> node = null;
T data = list.removeFirst();
if (data != null) {
node = new TreeNode<>(data);
node.leftChild = createBinaryNode(list);
node.rightChild = createBinaryNode(list);
}
return node;
}
/**
* 二叉树的前序遍历，用递归实现
* @param node 需要遍历的节点
* @param <T> 二叉树存储的数据对象类型
*/
public static <T> void preOrderTraversalByRecursion(TreeNode<T> node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrderTraversalByRecursion(node.leftChild);
preOrderTraversalByRecursion(node.rightChild);
}
/**
* 二叉树的中序遍历，用递归实现
* @param node 需要遍历的节点
* @param <T> 二叉树存储的数据对象类型
*/
public static <T> void midOrderTraversalByRecursion(TreeNode<T> node) {
if (node == null) {
return;
}
midOrderTraversalByRecursion(node.leftChild);
System.out.print(node.data + " ");
midOrderTraversalByRecursion(node.rightChild);
}
/**
* 二叉树的后序遍历，用递归实现
* @param node 需要遍历的节点
* @param <T> 二叉树存储的数据对象类型
*/
public static <T> void postOrderTraversalByRecursion(TreeNode<T> node) {
if (node == null) {
return;
}
postOrderTraversalByRecursion(node.leftChild);
postOrderTraversalByRecursion(node.rightChild);
System.out.print(node.data + " ");
}
/**
* 二叉树的前序遍历，用栈实现
*
* 这种实现类似于图的深度优先遍历（DFS）。维护一个栈，将根节点入栈，然后只要
* 栈不为空，出栈并访问，接着依次访问节点的右节点、左节点入栈。
*
* 这种方式应该是对前序遍历的一种特殊实现（看上去简单明了），但是不具备很好的
* 扩展性，在中序遍历和后序遍历方式中不适用
*
* @param root 需要遍历的根节点
* @param <T> 二叉树存储的数据对象类型
*/
public static <T> void preOrderTraversalByStack(TreeNode<T> root) {
if (root == null) {
return;
}
Stack<TreeNode<T>> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode<T> node = stack.pop();
System.out.print(node.data + " ");
if (node.rightChild != null) {
stack.push(node.rightChild);
}
if (node.leftChild != null) {
stack.push(node.leftChild);
}
}
}
/**
* 二叉树的前序遍历，用栈实现
*
* 利用栈模拟递归过程实现循环前序遍历二叉树，这种方式具有扩展性，它模拟递归的
* 过程，将左子树节点不断压入栈，直到 <code>null</code>，然后再处理栈顶节点
* 的右子树。
*
* @param root 需要遍历的根节点
* @param <T> 二叉树存储的数据对象类型
*/
public static <T> void preOrderTraversalByStack2(TreeNode<T> root) {
if (root == null) {
return;
}
Stack<TreeNode<T>> stack = new Stack<>();
TreeNode<T> node = root;
while (node != null || !stack.isEmpty()) {
// 访问节点的的左孩子，并入栈
while (node != null) {
System.out.print(node.data + " ");
stack.push(node);
node = node.leftChild;
}
// 如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
if (!stack.isEmpty()) {
node = stack.pop();
node = node.rightChild;
}
}
}
/**
* 二叉树的中序遍历，用栈实现
*
* 利用栈模拟递归过程实现循环中序遍历二叉树，思想和上面先序非递归2
* {@link #preOrderTraversalByStack2(TreeNode)} 相同，只是访问的时间是在
* 左子树都处理完 <code>null</code> 的时候出栈并访问
*
* @param root 需要遍历的根节点
* @param <T> 二叉树存储的数据对象类型
*/
public static <T> void midOrderTraversalByStack(TreeNode<T> root) {
if (root == null) {
return;
}
Stack<TreeNode<T>> stack = new Stack<>();
TreeNode<T> node = root;
while (node != null || !stack.isEmpty()) {
// 访问节点的的左孩子，并入栈
while (node != null) {
stack.push(node);
node = node.leftChild;
}
// 如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
if (!stack.isEmpty()) {
node = stack.pop();
System.out.print(node.data + " ");
node = node.rightChild;
}
}
}
/**
* 二叉树的后序遍历，用栈实现，额外借助一个 {@link TagNode} 类来实现标记。
*
* 后续遍历不同于先序和中序，它是要先处理完左子树和右子树，然后再处理根节点（回溯）
*
* 对于任一节点p，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子出现
* 的节点，此时该节点还未出现在栈顶，但是此时不能将其出栈并访问，因为其右孩子还
* 未被访问。
*
* 所以接下来按照相同的规则对其右子树进行相同的处理，当访问完右子树时，该节点又
* 出现在栈顶，此时可以将其出栈并访问，这样就保证了正确的访问顺序。
*
* 可以看出，在这个过程中，每个节点都两次出现在栈顶，只有第二次出现在栈顶时，才能
* 访问它。因此需要多设置一个变量标识该节点是否第一次出现在栈顶，这里是在树结构里
* 加一个标记，然后合成一个新的 {@link TagNode} 。
*
* @param root 需要遍历的根节点
* @param <T> 二叉树存储的数据对象类型
*/
public static <T> void postOrderTraversalByStack(TreeNode<T> root) {
if (root == null) {
return;
}
Stack<TagNode<T>> stack = new Stack<>();
TreeNode<T> node = root;
TagNode<T> tagNode;
while (node != null || !stack.isEmpty()) {
// 沿着左子树一直往下搜索，直至出现没有左孩子的节点
while (node != null) {
tagNode = new TagNode<>();
tagNode.treeNode = node;
tagNode.isFirst = true;
stack.push(tagNode);
node = node.leftChild;
}
if (!stack.isEmpty()) {
tagNode = stack.pop();
// 表示第一次出现在栈顶
if (tagNode.isFirst) {
tagNode.isFirst = false;
stack.push(tagNode);
node = tagNode.treeNode.rightChild;
} else {
//第二次出现在栈顶
System.out.print(tagNode.treeNode.data + " ");
node = null;
}
}
}
}
/**
* 二叉树的后序遍历，用栈实现，无需额外借助其它类来判断节点是否访问。
*
* 要保证根节点在左孩子和右孩子访问之后才能访问，因此对于任一节点p，先将其入栈。
* 如果p不存在左孩子和右孩子，则可以直接访问它。
*
* 或者p存在左孩子和或右孩子，但其左孩子和右孩子都已经被访问过了，则同样可以直接
* 访问该节点。
*
* 若非上述两种情况，则将p的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的
* 时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根节点前面被访问。
*
* @param root 需要遍历的根节点
* @param <T> 二叉树存储的数据对象类型
*/
public static <T> void postOrderTraversalByStack2(TreeNode<T> root) {
if (root == null) {
return;
}
Stack<TreeNode<T>> stack = new Stack<>();
TreeNode<T> currentNode = null, preNode = null;
stack.push(root);
while (!stack.isEmpty()) {
currentNode = stack.peek();
// 如果当前节点没有孩子节点或者孩子节点都已经被访问过
boolean isLeafNode = currentNode.leftChild == null && currentNode.rightChild == null;
boolean isVisited = (preNode != null && (preNode == currentNode.leftChild
|| preNode == currentNode.rightChild));
if (isLeafNode || isVisited) {
System.out.print(currentNode.data + " ");
stack.pop();
preNode = currentNode;
} else {
if (currentNode.rightChild != null) {
stack.push(currentNode.rightChild);
}
if (currentNode.leftChild != null) {
stack.push(currentNode.leftChild);
}
}
}
}
/**
* 二叉树的层级遍历，使用队列实现
* @param root 需要遍历的根节点
* @param <T> 二叉树存储的数据对象类型
*/
public static <T> void levelOrderTraversalByQueue(TreeNode<T> root) {
Queue<TreeNode<T>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode<T> node = queue.poll();
System.out.print(node.data + " ");
if (node.leftChild != null) {
queue.offer(node.leftChild);
}
if (node.rightChild != null) {
queue.offer(node.rightChild);
}
}
}
/**
* 二叉树的层级遍历，使用递归实现，对层级相同的节点进行输出
* @param root 需要遍历的根节点
* @param <T> 二叉树存储的数据对象类型
*/
public static <T> void levelOrderTraversalByRecursion(TreeNode<T> root) {
int depth = depth(root);
for (int i = 0; i < depth; i++) {
doLevelOrderTraversalByRecursion(root, 0, i);
}
}
/**
* 对二叉树相同层级的节点进行递归输出
* @param node 需要遍历的根节点
* @param level 遍历层级
* @param target 目标层级
* @param <T> 二叉树存储的数据对象类型
*/
private static <T> void doLevelOrderTraversalByRecursion(TreeNode<T> node, int level, int target) {
if (node == null) {
return;
}
if (level == target) {
System.out.print(node.data + " ");
}
doLevelOrderTraversalByRecursion(node.leftChild, level + 1, target);
doLevelOrderTraversalByRecursion(node.rightChild, level + 1, target);
}
/**
* 求二叉树的深度
* @param root 需要遍历的根节点
* @return 二叉树的根节点
*/
private static int depth(TreeNode root) {
if (root == null) {
return 0;
}
return Integer.max(depth(root.leftChild), depth(root.rightChild)) + 1;
}
public static void main(String[] args) {
// 构建二叉树
LinkedList<Integer> list = new LinkedList<>(Arrays.asList(3, 2, 9, null, null,
10, null, null, 8, null, 4));
TreeNode<Integer> root = createBinaryNode(list);
System.out.print("前序遍历(递归)：");
preOrderTraversalByRecursion(root);
System.out.println();
System.out.print("中序遍历(递归)：");
midOrderTraversalByRecursion(root);
System.out.println();
System.out.print("后序遍历(递归)：");
postOrderTraversalByRecursion(root);
System.out.println();
System.out.print("前序遍历1(栈)：");
preOrderTraversalByStack(root);
System.out.println();
System.out.print("前序遍历2(栈)：");
preOrderTraversalByStack2(root);
System.out.println();
System.out.print("中序遍历(栈)：");
midOrderTraversalByStack(root);
System.out.println();
System.out.print("后序遍历1(栈)：");
postOrderTraversalByStack(root);
System.out.println();
System.out.print("后序遍历2(栈)：");
postOrderTraversalByStack2(root);
System.out.println();
System.out.print("层级遍历(队列)：");
levelOrderTraversalByQueue(root);
System.out.println();
System.out.print("层级遍历(递归)：");
levelOrderTraversalByRecursion(root);
System.out.println();
}
}