前言
众所周知，二叉树的结点是由三个基本元素（根结点，左子树，右子树）组成的。因此，只要能依次遍历这三个元素，就能遍历整个二叉树。
若限定先左后右，那么只有三种访问方式：
1. 先序
先访问根结点，再访问左子树，最后右子树
2. 中序
先访问左子树，再访问根结点，最后右子树
3. 后序
先访问左子树，再访问右子树，最后根结点
满二叉树（图来自维基百科）
基于递归实现
先序
用前言的图作为例子
先序递归示例代码
public List<Integer> recursion(TreeNode root) {
List<Integer> list = new LinkedList<>();
if (null == root) {
return list;
}
// 先根结点
list.add(root.getVal());
if (null != root.getLeft()) {
// 左子树
list.addAll(recursionPrint(root.getLeft()));
}
if (null != root.getRight()) {
// 右子树
list.addAll(recursionPrint(root.getRight()));
}
return list;
}
先序运行结果
中序
用前言的图作为例子
中序递归示例代码
public List<Integer> recursion(TreeNode root) {
List<Integer> list = new LinkedList<>();
if (null == root) {
return list;
}
if (null != root.getLeft()) {
// 左子树
list.addAll(recursion(root.getLeft()));
}
// 根结点
list.add(root.getVal());
if (null != root.getRight()) {
// 右子树
list.addAll(recursion(root.getRight()));
}
return list;
}
中序运行结果
后序
用前言的图作为例子
后序递归示例代码
public List<Integer> recursion(TreeNode root) {
List<Integer> list = new LinkedList<>();
if (null == root) {
return list;
}
if (null != root.getLeft()) {
// 左子树
list.addAll(recursion(root.getLeft()));
}
if (null != root.getRight()) {
// 右子树
list.addAll(recursion(root.getRight()));
}
// 根结点
list.add(root.getVal());
return list;
}
后序运行结果
非递归实现
用递归可以让程序更加简洁，对于树结构的数据处理也十分便利。但是循环的效率往往比递归更优异。因此，有时我们需要将递归转化成非递归。当然有些编译器支持尾递归优化，可以选择使用尾递归（笔者使用的是 JDK8，这个版本不支持尾递归优化）。
先序
用前言的图作为例子
示例代码
public List<Integer> unRecursion(TreeNode root) {
List<Integer> list = new LinkedList<>();
// 游标初始化指向整棵树的根结点
TreeNode current = root;
// 通过栈的特性实现递归的回溯能力
Stack<TreeNode> stack = new Stack<>();
while (null != current || !stack.isEmpty()) {
while (null != current) {
// 加载结点
list.add(current.getVal());
stack.push(current);
// 游标指向左节点
current = current.getLeft();
}
if (!stack.isEmpty()) {
// 回到前驱节点
current = stack.pop();
// 游标指向右节点
current = current.getRight();
}
}
return list;
}
非递归先序遍历运行结果
中序
用前言的图作为例子
示例代码
public List<Integer> unRecursion(TreeNode root) {
List<Integer> list = new LinkedList<>();
// 游标初始化指向整棵树的根结点
TreeNode current = root;
// 通过栈的特性实现递归的回溯能力
Stack<TreeNode> stack = new Stack<>();
while (null != current || !stack.isEmpty()) {
while (null != current) {
stack.push(current);
// 游标指向左节点
current = current.getLeft();
}
if (!stack.isEmpty()) {
// 回到前驱节点
current = stack.pop();
// 加载结点
list.add(current.getVal());
// 游标指向右节点
current = current.getRight();
}
}
return list;
}
非递归中序运行结果
后序
用前言的图作为例子
示例代码
public List<Integer> unRecursion(TreeNode root) {
List<Integer> list = new LinkedList<>();
// 游标初始化指向整棵树的根结点
TreeNode current = root;
// 通过栈的特性实现递归的回溯能力
Stack<TreeNode> stack = new Stack<>();
// 由于后序遍历的特性决定了结点需要第二次出栈才可以被加载
Map<TreeNode, Integer> map = new HashMap<>();
while (null != current || !stack.isEmpty()) {
while (null != current) {
stack.push(current);
// 游标指向左节点
current = current.getLeft();
}
if (!stack.isEmpty()) {
TreeNode pop = stack.pop();
Integer count = map.getOrDefault(pop, 0);
if (count == 0) {
// 第一次出栈
current = pop.getRight();
stack.push(pop);
map.put(pop, count + 1);
} else {
// 第二次出栈
list.add(pop.getVal());
}
}
}
return list;
}
非递归后序运行结果
后序可能会绕一点，为什么是第二次出栈时才加载呢？
先想下递归，递归很容易就解决了，是因为我们将无数次场景的规模缩小，但是对于每一个结点的处理逻辑其实是一样的。这时我们想将递归转化成非递归，要用循环解决，那么我们也需要模仿递归的思路去做。显然，后序决定了根结点需要第二次访问才能加载，那么为了可以“一套逻辑打天下”，就需要所有结点都是第二次访问才加载。
按层遍历树
前面都是将一颗大树拆成一颗小树，然后再将最单元小树的三元素访问，从而遍历的。本质上就是DFS的处理方式。现在采取BFS的方式遍历。用前言的图作为例子
示例代码
public List<Integer> ergodicByBfs(TreeNode root) {
if (null == root) {
return new ArrayList<>(0);
}
List<Integer> list = new LinkedList<>();
// 一层层的遍历可以通过队列的特性实现，想象成按顺序拿珠子穿就好
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
// 加载元素
list.add(current.getVal());
if (null != current.getLeft()) {
// 将左孩子加入队列
queue.add(current.getLeft());
}
if (null != current.getRight()) {
// 将右孩子加入队列
queue.add(current.getRight());
}
}
return list;
}
按层遍历运行结果
线索二叉树
前面为了遍历二叉树，不是递归，就是用了栈或者队列。如果数据结构可以更丰富些，那么我们实现起来就不用那么麻烦。这也很好地体现了一个合理的数据结构设计是多么的重要。
不管递归，还是栈，核心思想还是一条路走到黑，到了头再回到上一个结点（回溯），再往另一条路走。为了达到这个效果，使用了递归和栈的特性实现而已。如果每个结点都有额外信息可以存储前驱节点和后继结点的信息，那么实现起来就简单多了。因此，有了线索二叉树。
将二叉树转化成线索二叉树的本质就是将非线性结构的数据进行线性化操作，使得每个结点（除头结点和尾结点外）在这线性序列中有且仅有一个直接前驱和直接后继。
看图更直接，大家可以对比下上面代码处理的二叉树的数据结构和线索二叉树的数据结构，如下图
只有三个基本元素的二叉树数据结构
线索二叉树数据结构
对于先序，中序，后序这三种遍历，线索化得到的结果也是不同的，具体如下
还没线索化的二叉树
先序遍历的结果应为：1 2 4 7 3 5 6
先序索引二叉树
中序遍历的结果应为：4 7 2 1 5 3 6
中序索引二叉树
后序遍历的结果应为：7 4 2 5 6 3 1
后序索引二叉树
总结：
1. 当结点数是 n 时，额外存储了 2n 个引用（因为我们定义 TreeNode 一般都用同一个，所以头结点的前驱是 null，尾结点的后继是 null）
2. 当结点数是 n 时，其中 n-1 个引用存储着后继结点；还剩 n+1 个空引，用可用于记录需要回溯的前驱节点
3. 为什么需要增加 leftType & rightType？因为二叉树本身的 left 和 right 指的是左孩子和右孩子，当我们线性化以后，可能会造成当前结点的 left、right 不再是“孩子”的含义。这时，就需要使用一个 type 来标识。
将一颗二叉树线索化的示例代码
前序
@Data
public class ThreadTreeNode {
private int data;
private int leftType;
private ThreadTreeNode left;
private int rightType;
private ThreadTreeNode right;
public ThreadTreeNode(int data) {
this.data = data;
}
public ThreadTreeNode(int data, ThreadTreeNode left, ThreadTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
public static ThreadTreeNode inThreading(ThreadTreeNode node) {
if (null == node) {
return null;
}
ThreadTreeNode leftNode = node.getLeft();
ThreadTreeNode rightNode = node.getRight();
node.setLeftType(0);
node.setLeft(null);
if (null != leftNode) {
ThreadTreeNode threadLeftNode = inThreading(leftNode);
threadLeftNode.setLeftType(1);
threadLeftNode.setLeft(node);
node.setRightType(1);
node.setRight(threadLeftNode);
}
if (null != rightNode) {
ThreadTreeNode threadRightNode = inThreading(rightNode);
threadRightNode.setLeftType(1);
if (0 == node.getRightType()) {
threadRightNode.setLeft(node);
node.setRightType(1);
node.setRight(threadRightNode);
} else {
ThreadTreeNode lastNode = node.getRight().getLastNode();
threadRightNode.setLeft(lastNode);
lastNode.setRightType(1);
lastNode.setRight(threadRightNode);
}
}
return node;
}
private ThreadTreeNode getLastNode() {
ThreadTreeNode last = getRight();
while (null != last) {
if (null == last.getRight()) {
break;
}
last = last.getRight();
}
return last == null ? this : last;
}
public List<Integer> toDataList() {
List<Integer> list = new LinkedList<>();
list.add(getData());
ThreadTreeNode last = getRight();
while (null != last) {
list.add(last.getData());
if (null == last.getRight()) {
break;
}
last = last.getRight();
}
return list;
}
public static void main(String[] args) {
ThreadTreeNode root = new ThreadTreeNode(
1,
new ThreadTreeNode(
2,
new ThreadTreeNode(4, null, new ThreadTreeNode(7)),
null
),
new ThreadTreeNode(
3,
new ThreadTreeNode(5),
new ThreadTreeNode(6)
)
);
ThreadTreeNode threadTreeNode = ThreadTreeNode.inThreading(root);
List<Integer> list = threadTreeNode.toDataList();
System.out.println(JsonUtil.toJsonString(list));
System.out.println("done");
}
}
中序和后序就交由你们自己实现啦。
