上一节我们说过了树的相关定义，其实定义原本就是辅助我们理解和定义的，一种数据结构存在的原因是在于其应用价值，而并非定义本身。那么这一篇文章就来讲讲，大学的时候讲过的，书上讲过的，网上讲过的，面试题问过... 二叉树的四种遍历方式：前序遍历，中序遍历，后序遍历，层级遍历。跟网上一些文章不同的是，本文从层级遍历这种相对比较简单的遍历方法来写起，也算是辅助理解吧。并放上一段讲解非常好的视频连接，我在 B站 学编程之: 二叉树遍历
前文讲到表示一个数的结点的三种方法，「双亲表示法」，「孩子弟兄表示法」，「孩子表示法」。这里采用最常见用的孩子兄弟表示法来表示一个二叉树：
/**
* 孩子兄弟法表示一个二叉树
*/
public class TreeNode<T> {
public T data;
public TreeNode<T> leftChild;
public TreeNode<T> rightChild;
public TreeNode(T data) {
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
}然后我们可以创建一个二叉树：
public class BinaryTreeUtils {
public TreeNode root = null;
public BinaryTreeUtils() {
root = new TreeNode<String>( "A");
}
/**
* 二叉树的构建首先需要跟节点，一般在构造方法里面创建
*/
public TreeNode createBinaryTree() {
TreeNode nodeB = new TreeNode<>("B");
TreeNode nodeC = new TreeNode<>("C");
TreeNode nodeD = new TreeNode<>("D");
TreeNode nodeE = new TreeNode<>("E");
TreeNode nodeF = new TreeNode<>("F");
TreeNode nodeG = new TreeNode<>("G");
root.leftChild = nodeB;
root.rightChild = nodeC;
nodeB.leftChild = nodeD;
nodeB.rightChild = nodeE;
nodeC.leftChild = nodeF;
nodeC.rightChild = nodeG;
return root;
}
}我们可以知道我们构造出的二叉树样子是长这个样的：
A / \ B C / \ / \ D E F G
接下来就可以写我们的层级遍历函数了。
层级遍历是指以二叉树根节点为开始，一层一层从左到右一次访问各个节点的遍历方式。
层级遍历的思想是：利用队列的思想来遍历一个二叉树。 遇到节点将其放入队列，然后出队的时候将分别将其左子树和右子树按顺序入队 再依次出队。循环结束的条件是 队列为空且要入队的节点为空。
如 A 的孩子为 B(left) C(right) ， A 入队 A出队 B 入队 C 入队 B 出队 C 出队 循环结束。非常简单，那么看下代码实现：
// 这里假设二叉树元素类型为 String
public static void levelTraverse(TreeNode<String> root){
if (root == null){
System.out.print("二叉树为空二叉树");
return;
}
// 用于记录当前处理的结点
TreeNode curNode = root;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(curNode);
while (curNode != null && !queue.isEmpty()){
System.out.print(queue.poll().data + " ");
if (curNode.leftChild != null) {
queue.add(curNode.leftChild);
}
if (curNode.rightChild != null) {
queue.add(curNode.rightChild);
}
curNode = queue.peek();
}
}那么我们看下结果：
A B C D E F G
层级遍历是不是很简单，通过一个 While 循环就可以实现，假设二叉树中节点的个数为 n 则时间复杂度为 O(1) ，额外的空间复杂对为 O(n)
这里先放一个我对递归的启蒙视频 ：如何理解递归
古人常云：递归便于理解！ 我听见这句话简直就是心中冒出无数个 mmp 。老子为啥经常被递归搞得神魂颠倒，欲生欲死。其实递归如果写出来的确是便于理解，但是写递归和设计递归的过程其实是与人们常见的归纳思想不太一样的。比如说注明的递归问题 肥波纳妾兔子的问题（停！那叫斐波那契数列）.
3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
打一个正常人来讲，肯定是这样分析问题的：
n = 1 兔子个数为： 1, n = 2 兔子个数为： 1, n = 3 兔子个数为： 3 ，n = 4 兔子个数为： 5 ，n = 6 兔子个数为： 7 .....
然后就啪啪啪的找 天数 n 与兔子个数的关系去了。这就是我们常说的归纳演绎法。那么天生的数学家头脑告诉我们不应该这样干其实规律很简单 F(n) = F(n - 1) + F(n -2) ; (n>2)。其实这个表达式就充分表明了递归这个思想。
说了那么多到底怎么理解递归呢？ 其实大多数教科书上还有网上的资料都对递归的定义是下边这样的：
递归思想：函数通过直接或者间接方式调用函数本身的过程。
有人认为我要反驳了？ Naive ！ 我只是想说明，这个定义没问题。but 就是不太便于理解。那么怎么去理解自己调用自己的这个形式呢？
我们都知道，函数可以嵌套调用。拿一个常见的例子来说：
private int[] sortArr(int[] arr){
....
}
int[] arr = {5,6,1,3,54,10};
public static void main(String[] args) {
int[] arr = sortArr(arr);
System.out.print(arr);
}上述过程在 main 函数中调用了，sortArr 方法，然后执行输出语句。 ok 没问题，这么简单大家都明白。那么其实这就是一个函数嵌套调用过程。jvm 调用 main 函数 ，main 函数中又调用 sortArr 方法，然后又回到 main 函数执行输出语句。
聪明的小伙伴看到回到这个词其实就明白了。其实在嵌套调用的过程实际上是：虚拟机为 每个函数执行开辟一个新的内存空间，待函数执行完成后又 回到之前的内存空间去执行接下来的语句。如下图所示：
概念理解了，但是对于能够使用递归来说还是远远不够的，比如说我们现在考一个 汉诺塔问题，我相信没有几个能够写起来的。面对一个问题，设计一种递归方法这本身就并非简单的问题。
递归，其实是分而治之的一种思想表现，分析一些规律的问题的时候我们总是可以找到一个最小问题集，比如快速排序的算法其实就是运用分而治之的思想，把一个数组对半分，再把分完的对半分，直到一组就剩下两个元素的是我们比较大小然后排序。递归思想需要理解，更需要掌握用递归求解的思维途径。这个路还很长，我们一起走下去吧。
上边把递归解释完了。怎么样是不是恍然大悟，然后说：嗯~ 古人说递归便于理解有道理！ 然后微笑着透着一丝 mmp。
其实递归的使用过程中，我们会造成很多额外的空间浪费。其实这就是递归的一缺点。
学习二叉树必定要学习其遍历过程，上边我们说过了利用队列思想去层级遍历二叉树。把每个节点都看成根节点，每个节点出队列的时候要看看自己有没有左孩子和右孩子，如果有则依次进站，然后开始将队列的队头当做根节点出站...依次循环完成整个遍历过程。
其实对于递归来遍历来说，大部分人可能背都能背下来，但是为什么递归这样就能实现呢？我们下边来对前中后三种递归遍历二叉树的方法分析一下，废话不多说先上代码：
###前序遍历：
所谓的前序遍历就是：先访问根节点，然后在访问左，再访问右节点的过程。
/**
* 递归先序遍历 根左右
*
* @param root
*/
public static void beforeTraverse(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.data + " ");
beforeTraverse(root.leftChild);
beforeTraverse(root.rightChild);
}
实话说我刚开始看到这段代码的感觉是，一个函数内部递归调用了自己两次，从表面上看是根左右的顺序。那么为啥这样就能成功呢? 我们来看一张图拿一个简单的3层二叉树来看：
3 2 1 4 5 5
那么对于上边这个二叉树递归是怎么调用的呢？建议同学们自己去拿笔画一下，这样便于思考。下边用一个图来描述一下：