主要记录一下对于二叉树，进行遍历的几种方式，包括：
- 前序遍历
- 中序遍历
- 后序遍历
- 深度优先遍历
- 广度优先遍历
我们以下面的这个二叉树结构为例，分别描述一下这几种遍历的方式有什么不同，以及给出java实现的代码。
几种遍历的区别
我们知道，一个二叉树有根节点，左节点，左节点。
我们遍历的顺序肯定先是左节点，再右节点。前序、中序、后序的区别就是根节点的位置。
如果根节点在左节点前面，那么就是前序遍历。
如果根节点在两者之间，那么就是中序遍历。对于二叉搜索树而言，中序遍历得到的结果是从小到大的。
如果根节点在右节点后面，那么就是后序遍历了。
对于深度优先，我们对于一棵树，从根节点开始，一直访问左子节点，一直到为空，再向上依次返回访问右子节点。以上面的树结构为例，它访问的顺序为: A,B,D,H,I,E,C,F,J,G。
对于广度优先，我们把树分层，根节点为第一层，根节点的子节点为第二层，第二层的子节点为第三层，依次递推。遍历的时候就对每一层进行依次访问。上面的树结构的遍历结果为：A,B,C,D,E,F,G,H,I,J
代码实现
前序遍历
遍历打印
public void prologuePrint(TreeNode root) {
if (root == null) {
return;
}
prologuePrint(root.left);
System.out.print(root.val + " ");
prologuePrint(root.right);
}
遍历，将数据添加到集合中
public List prologueList(TreeNode root) {
List result = new ArrayList();
prologueListHelp(root, result);
return result;
}
private void prologueListHelp(TreeNode node, List list) {
if (node == null) {
return;
}
prologueListHelp(node.left, list);
list.add(node.val);
prologueListHelp(node.right, list);
}
中序遍历
遍历打印
public void middlePrint(TreeNode root) {
if (root == null) {
return;
}
middlePrint(root.left);
System.out.print(root.val + "");
middlePrint(root.right);
}
遍历将数据添加到集合中
public List middleList(TreeNode root) {
List result = new ArrayList();
middleListHelp(root, result);
return result;
}
private void middleListHelp(TreeNode node, List list) {
if (node == null) {
return;
}
middleListHelp(node.left, list);
list.add(node.val);
middleListHelp(node.right, list);
}
后序遍历
遍历打印
public void postPrint(TreeNode root) {
if (root == null) {
return;
}
postPrint(root.left);
System.out.print(root.val + " ");
postPrint(root.right);
}
遍历将数据添加到集合中
public List postList(TreeNode root) {
List result = new ArrayList();
postListHelp(root, result);
return result;
}
private void postListHelp(TreeNode node, List list) {
if (node == null) {
return;
}
prologueListHelp(node.left, list);
list.add(node.val);
prologueListHelp(node.right, list);
}
深度优先遍历
用栈实现深度优先遍历
public static void DFSPrint(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " ");
//由于栈，先进后出，所以先放右节点
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
广度优先遍历
用队列实现广度优先遍历
public static void BFSPrint(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
//先进先出，先放左节点，再放右节点。遍历的时候就是每一层从左到右的顺序
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
本文由博客一文多发平台 OpenWrite 发布！
博主邮箱：liunaijie1996@163.com，有问题可以邮箱交流。
