为什么要学习树的遍历算法
二叉树的遍历方式有多种，根据每种遍历方式的不同特性，在现实中有着不同的应用价值
随着我们学得越深入越底层，就会发现二叉树的应用无处不在，很多基础技术，底层都是通过二叉树实现的
比如数据库系统、文件系统、编译系统、组织架构展示等等
我们先掌握每种遍历算法，以后再学习其具体应用时，就很容易理解了
广度优先遍历和深度优先遍历
二叉树遍历方式整体分为两大类
- 广度优先遍历，Breadth First Search，简称BFS遍历 这种方式先访问父节点，再访问父节点所有的直接子节点，再按此方式，对每个直接子节点下面的子树进行递归遍历
- 深度优先遍历，Depth First Search，简称DFS遍历 深度遍历分为好几种方式，它们的共同特征是，先遍历完一个节点下面的整个子树，再遍历下个同级节点的子树
- 广度遍历和深度遍历的区别，可以简单概括为，广度遍历是先遍历同级节点，深度遍历是先遍历当前节点子树
深度优先遍历的几种方式
上面已经提到，深度优先遍历是先遍历当前子树，再遍历同级节点
而子树如何遍历，根据父节点的访问顺序，可分为三种方式
- 先序遍历，Preorder Traversal 按父节点-左子树-右子树的顺序，遍历每个节点所在的树
- 中序遍历，Inorder Traversal 按左子树-父节点-右子树的顺序，遍历每个节点所在的树
- 后序遍历，Postorder Traversal 按左子树-右子树-父节点的顺序，遍历每个节点所在的树
定义树和测试数据
我们先构建这样的一颗树，作为测试数据，然后再分别以不同的遍历算法，来遍历该树
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
@SuppressWarnings("all")
public class TreeNode {
//树深度
public Integer depth = 0;
//数值
public T data = null;
//添加transient关键字，是告诉JSON等序列化功能，在序列化时忽略此字段
//父节点包含子节点，字节点也包含父节点，对象之间相互循环引用，会导致序列化时产生死循环
//可以通过transient来忽略parentNode字段，通过parentId来查找
public transient TreeNode parent;
public final LinkedList children = new LinkedList();
//添加子节点
public void add(TreeNode child) {
child.parent = this;
child.depth = depth + 1;
children.addLast(child);
}
//移除子节点
public void remove(TreeNode child) {
child.parent = null;
child.depth = null;
children.remove(child);
}
//添加子节点
public void add(T data) {
TreeNode child = new TreeNode();
child.data = data;
child.parent = this;
child.depth = depth + 1;
children.addLast(child);
}
//移除子节点
public void remove(T data) {
List deleteNodes = new LinkedList();
for (TreeNode child : children)
if (Objects.equals(child.data, data)) {
child.parent = null;
child.depth = null;
deleteNodes.add(child);
}
children.removeAll(deleteNodes);
}
//打印当前子树
@Override
public String toString() {
String childDescription = "";
if (!children.isEmpty()) {
childDescription = childDescription + "（";
for (TreeNode child : children)
childDescription = childDescription + child.data;
childDescription = childDescription + "）";
}
return data + childDescription;
}
}
import java.util.List;
//遍历parentNode，将其所有节点按遍历顺序存到resultList当中
public interface ITreeTraverser {
void traverse(TreeNode parentNode, List resultList);
}
import java.util.LinkedList;
import java.util.List;
public class Demo {
public static TreeNode createTree() {
TreeNode a = new TreeNode();
a.data = "A";
TreeNode b = new TreeNode();
b.data = "B";
TreeNode c = new TreeNode();
c.data = "C";
TreeNode d = new TreeNode();
d.data = "D";
TreeNode e = new TreeNode();
e.data = "E";
TreeNode f = new TreeNode();
f.data = "F";
TreeNode g = new TreeNode();
g.data = "G";
a.add(b);
a.add(c);
b.add(d);
b.add(e);
c.add(f);
c.add(g);
return a;
}
public static void main(String[] args) {
TreeNode tree = createTree();
List list = new LinkedList();
ITreeTraverser traverser = new XXXTraverserImpl();
traverser.traverse(tree, list);
for (TreeNode node : list)
System.out.println(node);
}
}
广度优先遍历代码实现
import java.util.LinkedList;
import java.util.List;
public class BreadthTraversal implements ITreeTraverser {
public void traverse(TreeNode parentNode, List resultList) {
List levelNodeList = new LinkedList();
levelNodeList.add(parentNode);
traverse(levelNodeList, resultList);
}
//当前层次的所有节点
private void traverse(List levelNodeList, List resultList) {
if (levelNodeList.isEmpty())
return;
resultList.addAll(levelNodeList);
List nextLevelNodeList = new LinkedList();
for (TreeNode node : levelNodeList)
nextLevelNodeList.addAll(node.children);
traverse(nextLevelNodeList, resultList);
}
}
打印结果
A（BC） B（DE） C（FG） D E F G
先序遍历代码实现
import java.util.List;
public class PreorderTraversal implements ITreeTraverser {
public void traverse(TreeNode parentNode, List resultList) {
resultList.add(parentNode);
if (parentNode.children.size() >= 1) {
TreeNode leftChild = parentNode.children.get(0);
traverse(leftChild, resultList);
}
if (parentNode.children.size() >= 2) {
TreeNode rightChild = parentNode.children.get(1);
traverse(rightChild, resultList);
}
}
}
打印结果
A（BC） B（DE） D E C（FG） F G
中序遍历代码实现
import java.util.List;
public class InorderTraversal implements ITreeTraverser {
public void traverse(TreeNode parentNode, List resultList) {
if (parentNode.children.size() >= 1) {
TreeNode leftChild = parentNode.children.get(0);
traverse(leftChild, resultList);
}
resultList.add(parentNode);
if (parentNode.children.size() >= 2) {
TreeNode rightChild = parentNode.children.get(1);
traverse(rightChild, resultList);
}
}
}
打印结果
D B（DE） E A（BC） F C（FG） G
后序遍历代码实现
import java.util.List;
public class PostorderTraversal implements ITreeTraverser {
public void traverse(TreeNode parentNode, List resultList) {
if (parentNode.children.size() >= 1) {
TreeNode leftChild = parentNode.children.get(0);
traverse(leftChild, resultList);
}
if (parentNode.children.size() >= 2) {
TreeNode rightChild = parentNode.children.get(1);
traverse(rightChild, resultList);
}
resultList.add(parentNode);
}
}
打印结果
D E B（DE） F G C（FG） A（BC）
遍历算法的基本应用
- 广度优先遍历：如果我们想遍历整个树，找到每一层的的最大值，这种方法是最简单直观的 比如大家开年会的时候，想要在每个级别分别选出若干个优秀员工，就可以采用这种算法
- 深度优先遍历：可用来解析数学公式或代码语句 比如我们要表达出a+b这种运算，就可以通过树来实现，a作为左节点，b作为右节点，+为父节点 这样+所在的子树，就可以代表a+b的运算结果，然后再与其它子树，继续进行运算，就实现了一个数学公式解释器
下一章，我们就要专门来讲解，如何通过树来存储和计算表达式
