在我们真实的世界里，到底是具体的数值重要，还是数值之间相对的大小关系更重要，或者说相对的次序更重要？我想绝大部分人会说：“这得看具体情况”，如果必须让你在上述问题中做出二选一的回答，你会怎么办？

具体到上面这个问题，在计算机科学中其实是有明确答案的，那就是相对的大小要比绝对的数值更重要。这一点，计算机科学和数、理、化都不相同，在数学上，数字是准确的；在物理中，水的冰点有一个确切的温度，水不到0°是无法结冰的。但在计算机科学里并不是这样的，AlphaGo在和柯洁下棋时，讲解棋局的几位高手有时会觉得AlphaGo下得莫名其妙，因为明明有一步棋可以赢20目，它却要走一步稳妥的，原因其实很简单，计算机只看重相对的输赢。

世界上有什么样的问题，就有什么样的工具，或者说工具的发明是针对问题来的。在数学上要计算数字，人类就发明了算盘；在物理学上，要测量绝对的数值，人们就发明了各种度量长度的尺子、计时的钟、称重量的天平等；在化学上要测量化学反应的当量，人类就发明了各种有刻度的量器。在计算机中，由于经常要做的事情是判断真假、比较大小、排序、挑选最大值这类的操作，而它们在计算机的世界里又如此重要，当然也就值得为这些事情专门设计一种数据结构这种数据结构被称为二叉树。

你可以看一眼下面二叉树的图示，有一个感性的认识： 为了便于理解二叉树，我们可以将它和自然界的树木对应起来：

我们在生活中，一些组织结构其实就是树状结构，比如一个公司的大老板就是根节点，每一个部门的老板是主干的根，下面职能部门的总监是枝干的根，再下面小组的经理是更小枝子的根，最后基层员工是叶子结点。

接下来你可能会问，这种怪怪的数据结构在计算机科学中有什么用处呢？它的用途很多，比如说可以用于排序。我们在前面介绍的排序算法，无论是高效率的快速排序还是最直观的插入排序，使用的都是数组或者说线性的列表。其实，二叉树可以直接完成排序，因为它有一个很好的性质，就是它左右两个分叉可以和比较大小后的两种结果自然对应起来。具体讲，用二叉树排序的过程中只要遵循下面两条规则就可以了：

这样安排得出来的二叉树，里面的数字从左到右自然是从小到大排好序的。假设共N个数字，每个数字按照一定的规则放到二叉树中的时间为logN（类似二分查找的时间复杂度分析），所有数字放进二叉树使其有序的总时间是NlogN，这个时间和快速排序是同一个量级的。

二叉树这种数据结构的用途远不止排序，前面举了排序的例子只是为了说明它有用，在现实的工程中，二叉树可以做很多事情，比如快速查找到某一个数值（二分查找，时间复杂度logN）。另外，由于网站的目录结构也是树状的（当然它们有N个分叉），因此针对二叉树的各种算法，稍加改变就可以用于互联网。比如我们找到一个网站后，要下载一个网站里面所有的网页，就会用到二叉树中的一种遍历算法。

二叉树虽然是一种抽象的东西，在自然界中并不存在，但是它却浓缩了自然界很多事物的共性，那就是分叉、层层递进和有序。而针对这些共性，科学家们又总结出一些具有普遍性的算法，能够回过头来，应用到各种实际问题中。

前面已经给出了二叉树的图示，二叉树是最常用的树结构，有二叉树自然就有三叉树、四叉树等其它数量分叉的树，那什么是“树”呢？再完备的定义，都没有图直观，下面给出几棵“树”的图示，这些“树”都有什么特征呢？ “树”这种数据结构真的很像我们现实生活中的“树”，这里面每个元素我们叫作“结点”；用连线来表示相邻结点之间的关系，我们叫作“父子关系”。比如下面这幅图，A 结点就是 B 结点的父结点，B 结点是 A 结点的子结点。B、C、D 这三个结点的父结点是同一个结点，所以它们之间互称为兄弟结点。我们把没有父结点的结点叫作根结点，也就是图中的结点 E。我们把没有子结点的结点叫作叶子结点或者叶结点，比如图中的 G、H、I、J、K、L 都是叶子结点。 除此之外，关于“树”，还有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。它们的定义是这样的：

这三个概念的定义比较容易混淆，描述起来也比较空洞，下面举个例子说明一下： 在我们的生活中，“高度”这个概念，其实就是从下往上度量，比如我们要度量第 10 层楼的高度、第 13 层楼的高度，起点都是地面。所以，树这种数据结构的高度也是一样，从最底层开始计数，并且计数的起点是 0。

“深度”这个概念在生活中是从上往下度量的，比如水中鱼的深度，是从水平面开始度量的。所以，树这种数据结构的深度也是类似的，从根结点开始度量，并且计数起点也是 0。

“层数”跟深度的计算类似，不过，计数起点是 1，也就是说根结点的位于第 1 层。

前面我们也说了，树结构多种多样，我们最常用却是二叉树。二叉树，顾名思义，每个结点最多有两个“叉”，也就是两个子结点，分别是左子结点和右子结点。不过，二叉树并不要求每个结点都有两个子结点，有的结点只有左子结点，有的结点只有右子结点。 上图中有两个比较特殊的二叉树，分别是编号 2 和编号 3 这两个。其中，编号 2 的二叉树中，叶子结点全都在最底层，除了叶子结点之外，每个结点都有左右两个子结点，这种二叉树就叫作满二叉树。编号 3 的二叉树中，叶子结点都在最底下两层，最后一层的叶子结点都靠左排列，并且除了最后一层，其他层的结点个数都要达到最大，这种二叉树叫作完全二叉树。

满二叉树的特征非常明显，我们把它单独拎出来，这个可以理解。但是完全二叉树的特征不怎么明显，单从长相上来看，完全二叉树并没有特别特殊的地方，更像是“芸芸众树”中的一种。那我们为什么还要特意把它拎出来呢？为什么偏偏把最后一层的叶子结点靠左排列的叫完全二叉树？如果靠右排列就不能叫完全二叉树了吗？这个定义的由来或者说目的在哪里？

要理解完全二叉树定义的由来，我们需要先了解，如何表示（或者存储）一棵二叉树？想要存储一棵二叉树，我们有两种物理存储结构，一种是基于数组的顺序存储法，另一种是基于指针或者引用的链式存储法。

我们先来看比较简单、直观的链式存储法，从图中你应该可以很清楚地看到，每个结点有三个字段，其中一个存储数据，另外两个是指向左右子结点的指针，我们只要拎住根结点，就可以通过左右子结点的指针，把整棵树都串起来。这种存储方式我们比较常用，大部分二叉树代码都是通过这种结构来实现的。

我们再来看，基于数组的顺序存储法，我们把根结点存储在下标 i = 1 的位置，那左子结点存储在下标 2 * i = 2 的位置，右子结点存储在 2 * i + 1 = 3 的位置。以此类推，B 结点的左子结点存储在 2 * i = 2 * 2 = 4 的位置，右子结点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。 如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子结点，下标为 2 * i + 1 的位置存储的就是右子结点。反过来，下标为 i/2 的位置存储就是它的父结点。通过这种方式，我们只要知道根结点存储的位置（一般情况下，为了方便计算子结点，根结点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。

刚刚举的例子是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间，你可以看下面几个例子。 如果使用游标数组来存储二叉树，二叉树结点可以定义如下：

所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子结点的指针，这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子结点都靠左的原因。我们后面要介绍的堆其实就是一种完全二叉树，最常用的存储方式就是数组。

一个数据结构的遍历操作是比较重要的，前面介绍的线性表遍历操作比较简单，需要注意的就是明确遍历起点与终点，防止遗漏或访问越界。二叉树结构比线性表复杂，如何将二叉树中所有结点都遍历打印出来呢？经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是结点与它的左右子树结点遍历打印的先后顺序。

实际上，二叉树的前、中、后序遍历就是一个递归的过程。比如，前序遍历，其实就是先打印根结点，然后再递归地打印左子树，最后递归地打印右子树。

写递归代码的关键，就是看能不能写出递推公式，而写递推公式的关键就是，如果要解决问题 A，就假设子问题 B、C 已经解决，然后再来看如何利用 B、C 来解决 A。你可能已经发现了，二叉树的结构很适合使用前面介绍的分治算法来处理，一棵二叉树有两个子叉，每个子叉也是一棵二叉树，因此二叉树可以使用递归不断分解为左右两个子二叉树去处理，递归的边界条件就是根结点为空。按照上面的逻辑，给出二叉树的前、中、后序遍历实现代码如下：