二叉树的基础---四种遍历方式的 Java 实现

0. 前言

大家好，我是多选参数的程序锅，一个正在“研究”操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇将带来的是二叉树的相关知识，知识提纲如图所示。

1. 基本介绍

树结构多种多样，但是最常用的还是二叉树。二叉树中每个节点最多有两个子节点，这两个节点分别是左子节点和右子节点。注意：不要求都有两个子节点，可以只有左子节点，也可以只有右子节点。

2. 二叉树的存储

2.1. 链式存储法

每个节点至少有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。这种存储方式比较常用，大部分二叉树代码都是通过这种结构来实现的。

2.2. 数组存储法

我们把根节点存储在下标 i=1 的位置，它的左子节点存储在下标为 2 * i 的位置，右子节点存储在下标为 2*i+1 的位置。以此类推，B 节点、C 节点的左右子节点都按照这种规律进行存储，最终如下图所示。

综上，如果节点 X 存储在数组中下标为 i 的位置，那么下标为 2*i 的位置存储的就是它的左子节点，下标为 2*i+1 的位置存储的就是它的右子节点。反过来，i/2 的位置存储的就是它的父节点。一般情况下，为了方便计算，根节点会被存储在下标为 1 的位置。

通过上述可以看到，针对一般树来说，使用数组的方式存储树会浪费比较多的存储空间。但是针对下文会提到的满二叉树或者完全二叉树来说，数组存储的方式是最节省内存的一种方式。因为数组存储时，不需要再存储额外的左右子节点的指针。

3. 二叉树的遍历

二叉树的遍历就是将二叉树中的所有节点遍历打印出来。经典的方法有三种，前序遍历、中序遍历和后序遍历，还可以按层遍历（个人理解的按层遍历其实就是按照图的广度优先遍历方法来进行遍历）。

前、中、后是根据节点被打印的先后来进行区分的：前序就是先打印节点本身，之后再打印它的左子树，最后打印它的右子树；中序就是先打印节点的左子树，再打印节点本身，最后打印右子树，即把节点放中间的位置输出；后序就是先打印节点的左子树，再打印节点的右子树，最后打印节点本身。如下图所示

按层遍历类似于图的广度优先遍历，先打印第一层的节点，之后再依次打印第二层的节点，以此类推。

3.1. 代码实现

实际上，二叉树的前、中、后序遍历是一个递归的过程。比如，前序遍历，其实就是先打印根节点，然后递归遍历左子树，最后递归遍历右子树。递归遍历左右子树其实就跟遍历根节点的方法一样。下面先写出这三者遍历的递推公式：

前序遍历的递推公式：
preOrder(r) = print r ---> preOrder(r->left) ---> preOrder(r->right)

中序遍历的递推公式：
inOrder(r) = inOrder(r--->left) ---> print r ---> inOrder(r->right)

后序遍历的递推公式：
postOrder(r) = postOrder(r->left) ---> postOrder(r->right) --->print r

之后将递推公式转化为代码如下所示：

/**
 * 前序遍历
 */
public void preOrder(Node tree) {
    if (tree == null) {
        return;
    }

    System.out.print(tree.data + "  ");

    preOrder(tree.left);

    preOrder(tree.right);
}

/**
 * 中序遍历
 */
public void inOrder(Node tree) {
    if (tree == null) {
        return;
    }

    inOrder(tree.left);

    System.out.print(tree.data + "  ");

    inOrder(tree.right);
}

/**
 * 后序遍历
 */
public void postOrder(Node tree) {
    if (tree == null) {
        return;
    }

    postOrder(tree.left);

    postOrder(tree.right);

    System.out.print(tree.data + "  ");
}

★递归代码的关键，在于写出递推公式。而递推公式的关键在于，A 问题可以被拆解成 B、C 两个问题。假设要解决 A 问题，那么假设 B、C 问题已经解决了。那么在 B、C 已经解决的提前下，看如何利用 B、C 来解决 A 。千万不要模拟计算机一层一层想下去，否则你就会发现你自己都不知道在哪了。 ”

下面是按层遍历的代码，按层遍历需要用到队列的入队和出队等操作。先将根节点放入到队列中，然后循环从队列中取节点（出队），再将该节点的左右子节点入队。出队的顺序就是层次遍历的结果。

/**
 * 层次遍历
 */
public void BFSOrder(Node tree) {
    if (tree == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();
    Node temp = null;
    queue.offer(tree);
    while (!queue.isEmpty()) {
        temp = queue.poll();
        System.out.print(temp.data + "  ");
        if (temp.left != null) {
            queue.offer(temp.left);
        }

        if (temp.right != null) {
            queue.offer(temp.right);
        }
    }
}

★完整的代码可查看 github 仓库 https://github.com/DawnGuoDev/algos ，这个仓库将主要包含常用数据结构及其基本操作的手写实现（Java），也会包含常用算法思想经典例题的实现（Java）。在程序锅找到工作之前，这个仓库将会保持更新状态，在此之间学到的关于数据结构和算法的知识或者实现也都会往里面 commit，所以赶紧来 star 哦。 ”

3.2. 时间复杂度

遍历过程中的次数就是访问所有节点的所需的次数，而每个节点最多被访问两次，因此遍历的时间复杂度是跟节点的个数 n 成正比的，即遍历的时间复杂度是 O(n)。

4. 特殊的二叉树

4.1. 满二叉树

满二叉树是一种特殊的二叉树，而且还是完全二叉树的一种特殊情况。如上图编号 2 的那棵树所示，叶子节点全在底层，除了叶子节点之外，每个节点都有左右两个子节点。

4.2. 完全二叉树

完全二叉树也是一种特殊的二叉树。如上图编号 3 的那棵树所示，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都达到最大。

完全二叉树的特征使得它可以使用数组就可以很好地存储数据。完全二叉树要求最后一层的叶子节点靠左排列也是因为如此。

4.2.1. 完全二叉树的存储

• 链式存储 就是上面提到的那种方式。
• 数组存储 完全二叉树使用数组存储时，如下图所示。我们发现使用数组来存储完全二叉树是一种很节省内存的方式。这也是完全二叉树被作为一种特殊树的原因，也是完全二叉树要求最后一层的子节点必须都靠左的原因。 在讲解堆或者堆排序的时候，堆其实也是一种完全二叉树，最常用的存储方式就是数组。

4.3. 其他特殊的二叉树

其他特殊的二叉树还有二叉查找树、平衡二叉查找树等。因为这两种特殊的树涵盖的知识比较多，所以会将其分开进行单独讲解。

5. 巨人的肩膀

1. 极客时间专栏，王争老师的《数据结构与算法之美》

6. 附 Github

整个系列的代码可查看 github 仓库 https://github.com/DawnGuoDev/algos ，这个仓库将主要包含常用数据结构及其基本操作的手写实现（Java），也会包含常用算法思想经典例题的实现（Java）。在接下来一年内，这个仓库将会保持更新状态，在此之间学到的关于数据结构和算法的知识或者实现也都会往里面 commit，所以赶紧来 star 哦。