树的遍历总结

本文总结一下树的几种遍历方法，分别是前序，前序非递归，中序，中序非递归，后序，后序非递归，按层次遍历，这7种。

前序遍历

先打印当前节点，再用前序遍历的方法遍历左右子树。

前序遍历非递归

遍历到当前节点，如果非空，打印这个节点，将其入栈，指向其左子节点，否则，出栈一个元素（这个元素的左子树遍历完毕），指向其右子节点。

中序遍历

用中序遍历的方法遍历左子树，打印当前节点，用中序遍历的方法遍历右子数。

中序遍历非递归

遍历到当前节点，如果非空，将其入栈，指向其左子节点，否则，出栈一个元素（这个元素的左子树遍历完毕），打印它，指向其右子节点。

后序遍历

用后序遍历的方法遍历左右子树，打印当前节点。

后序遍历非递归

用p指向栈顶结点，用last指向上一个打印的节点，满足下面的两个条件之一，p出栈，打印p并且更新last。条件1：p的左右节点都为空，条件2：last为p的左子节点或右子节点。否则，将p的右子节点入栈（如果不空），将p的左子节点入栈（如果不空）。注意，这里先右后左，因为栈后进先出。

按层遍历

使用队列，先将根节点入队（如果根节点不空），然后从队列中取出一个元素，将左子节点（不为空）入队，将右子节点（不为空）入队，依次类推，队列为空，遍历完毕。如果要按层打印的话，队列当前的元素个数就是本层的元素个数，举例，第一层元素个数为1，队列此时元素个数也为1。因为当一层遍历完之后，其实队列中剩下的元素也就是下一层的元素。

最后，上一下代码：

import java.util.*;

class TreeNode {
	TreeNode left;
	TreeNode right;
	int val;

	TreeNode(int val) {
		this.val = val;
	}
}

public class Tree {
	public static void main(String[] args) {
		TreeNode node1 = new TreeNode(5);
		TreeNode node2 = new TreeNode(3);
		TreeNode node3 = new TreeNode(2);
		TreeNode node4 = new TreeNode(9);
		TreeNode node5 = new TreeNode(4);
		TreeNode node6 = new TreeNode(6);
		TreeNode node7 = new TreeNode(8);
		TreeNode node8 = new TreeNode(7);
		node1.left = node2;
		node1.right = node3;
		node2.right = node4;
		node3.left = node5;
		node3.right = node6;
		node5.right = node7;
		node6.left = node8;
		System.out.println("前序遍历：");
		preOrder(node1);
		System.out.println("\n前序遍历非递归：");
		preOrderNot(node1);
		System.out.println("\n中序遍历：");
		inOrder(node1);
		System.out.println("\n中序遍历非递归：");
		inOrderNot(node1);
		System.out.println("\n后序遍历：");
		postOrder(node1);
		System.out.println("\n后序遍历非递归：");
		postOrderNot(node1);
		System.out.println("\n按层遍历并按层输出：");
		layerOrder(node1);

	}

	// 前序
	public static void preOrder(TreeNode root) {
		if (root == null) {
			return;
		}
		System.out.print(root.val + " ");
		preOrder(root.left);
		preOrder(root.right);
	}

	// 前序非递归
	public static void preOrderNot(TreeNode root) {
		Stack<TreeNode> s = new Stack<>();
		TreeNode p = root;
		while (p != null || !s.isEmpty()) {
			if (p != null) {
				System.out.print(p.val + " ");
				s.push(p);
				p = p.left;
			} else {
				p = s.pop();
				p = p.right;
			}
		}
	}

	// 中序
	public static void inOrder(TreeNode root) {
		if (root == null) {
			return;
		}
		inOrder(root.left);
		System.out.print(root.val + " ");
		inOrder(root.right);
	}

	// 中序非递归
	public static void inOrderNot(TreeNode root) {
		Stack<TreeNode> s = new Stack<>();
		TreeNode p = root;
		while (p != null || !s.isEmpty()) {
			if (p != null) {
				s.push(p);
				p = p.left;
			} else {
				p = s.pop();
				System.out.print(p.val + " ");//中序非递归和前序非递归的区别只是打印的位置不同
				p = p.right;
			}
		}
	}

	// 后序
	public static void postOrder(TreeNode root) {
		if (root == null) {
			return;
		}
		postOrder(root.left);
		postOrder(root.right);
		System.out.print(root.val + " ");
	}

	// 后序非递归
	public static void postOrderNot(TreeNode root) {
		Stack<TreeNode> s = new Stack<>();
		TreeNode p = root;
		TreeNode last = root;
		s.push(p);
		while (!s.isEmpty()) {
			p = s.peek();//取栈顶元素
			if ((p.left == null && p.right == null) || (last == p.left || last == p.right)) {//满足打印条件
				s.pop();//出栈
				System.out.print(p.val + " ");//打印
				last = p;//更新last
			} else {
				if (p.right != null) {
					s.push(p.right);
				}
				if (p.left != null) {
					s.push(p.left);
				}
			}

		}
	}

	// 按层遍历，并按层打印
	public static void layerOrder(TreeNode root) {
		LinkedList<TreeNode> q = new LinkedList<>();
		if (root != null) {
			q.offer(root);
		}
		while (!q.isEmpty()) {
			int size = q.size();//当前层的元素个数
			for (int i = 0; i < size; i++) {//打印当前层元素并将下一层元素入队
				TreeNode p = q.poll();
				System.out.print(p.val + " ");
				if (p.left != null) {
					q.offer(p.left);
				}
				if (p.right != null) {
					q.offer(p.right);
				}
			}
			System.out.println();//换行
		}
	}

}

输出结果：