树的概念

探索二叉树前，先来认识下什么是树？用官方一点的话来说，树是数据元素之间具有层次关系的非线性结构，是由n（n>=0）个节点组成的有限集合，n=0时称为空树。在任意一颗非空树中，它具有了以下特性：

• 每棵树至多只有一个根节点。

• 由根节点构造出多个孩子节点，每个孩子节点只有一个父节点，而孩子节点又构造出多个节点。

先看张图，方便了解下树的一些专业术语。

• 根节点：根节点是没有父节点，图中的A节点。

• 孩子节点/子节点：某个节点的孩子称为孩子节点，孩子节点/子节点是相对的，图中A的孩子节点有B、C、D，而B的孩子节点有E、F。

• 叶子节点：某个节点没有孩子，图中的E、F、G、D。

• 节点的度：某个节点的孩子节点个数，图中A有BCD（3）个孩子节点，B有EF（2）个孩子节点。

• 树的层次：某个节点处于树中的层次，图中的A处于第1层。

• 树的高/深度：树的最大层次，图中的高/深度为3。

接下来聊正题吧！

二叉树的概念

二叉树是由n（n>=0）个节点组成的有限集合，n=0时称为空树。在任意一颗非空树中，由一个根节点和两颗互不相交、分别称为根节点的左子树、右子树组成。简单来说，二叉树是一种特殊的树，每个节点最多只能有两个子节点，也就是左子树、右子树。比某个节点小的值放在该节点的左侧，称为左子树，该节点左侧的所有节点，包括子孙节点，都小于该节点，同理，比某个节点大的值放在该节点的右侧，称为右子树，右侧的所有节点都大于该节点的值，这是二叉树的特点！除了上面提到的特性，二叉树还有另外一些性质，提供一张图，方便理解与解释：

• 在二叉树的第K层上，最多有2^k-1个节点，假设k=3，即在第三层，最多有4个节点。

• 高/深为m的二叉树中，最多有2^m-1个节点，图中高/深度为3，那么最多7个节点，只差C节点的左子树。

• 在任意一颗二叉树中，度为0的节点总是比度为2的节点多1个，图中度为0的节点有DEF（3），而度为2的节点有AB（2）个。

• 具有n个节点的二叉树，其高/深度至少为log₂n + 1，图中共有6个节点，log₂6不会算的话，可以想想6是不是介于2²与2³之间，它应该无限接近于2次方，最后在加上1，所以高/深至少为3层。

满二叉树

在一颗二叉树中，每一层的节点数都达到最大个数，相当于是除了叶子节点外，其余节点都有左右子节点，以下是它的特性：

• 在满二叉树的第K层上，有2^k-1个节点。

• 高/深为m的二叉树中，有2^m-1个节点。

如图所示：

完全二叉树

在一颗二叉树中，除了最后一层外，其他各层的节点数都达到最大个数，且最后一层从左向右的节点连续存在，只缺右侧若干节点。该含义和满二叉树很相似，所以说满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树，以下是它的特性：

• 具有n个节点的二叉树，其高/深为log₂n + 1

如图所示：

二叉树的存储结构

顺序结构

二叉树的顺序结构是使用一维数组存储二叉树中的节点，如图所示：

上图中所采用的顺序存储结构如图所示：

仔细观察这是一颗完全二叉树，数组能够刚好填充数组，但对于不是完全二叉树又该是如何存储的？接着看图：

上图中所采用的顺序存储结构如图所示：

存储位置没有发生变化，只是在索引为4的位置上存储了空元素（^代表为空），表示此位置上是没有节点的？为什么要这么做呢？简单来说就是为了节点能够很容易地找到父节点或孩子节点，若没有按照一定的规则存储，压根不知道每个节点之间的关系，也就失去了二叉树的意义了。具体的规则如下：一棵树有n个节点，假设i（0 <= i < n）为某个节点的索引，那么该节点的左子树对应的数组索引是2i + 1，右子树对应的数组索引是2i + 2，而该节点的父节点对应的数组索引是(i - 1) / 2。通过以上的规则在数组中维护了每个节点之间的关系，但同时也会造成一定空间的浪费，就好比当它是空元素时，也只有在完全二叉树的情况下才不会造成空间的浪费，严格上来说，该存储方式一般适用于完全二叉树。

二叉链表

二叉树还有另外一种存储结构，链式存储结构，该结构可分为：二叉链表、三叉链表，下面将会分别说明。二叉链表结构主要由一个数据域和两个分别指向左右子树的节点组成，如图所示：

这很像单向链表，每个节点只存储了孩子节点的关系，若要找到其父节点需要重新遍历链表，那效率将被大大的降低了！因此为了提高效率，在原有的基础上新增了父节点的地址，称为三叉链表结构，如图所示：

两者的区别仅在于多了一个父节点的地址。

二叉树的设计与实现

尝试手写下二叉树，将采用二叉链表结构实现。由于作者对算法技术并不是很了解，该设计也是参考了别个文章的代码，不得不说，别人写的算法文章还是很专业，对于算法内容讲的很明白、清晰，但是对于代码上的设计并不是很友好，所以最终作者是自己设计了实现代码，只是放出了代码相关的图片，有兴趣的同学可以去github上观摩-二叉树设计，也顺便提一下别人的文章二叉树算法。

若只是想了解算法的话，可以看提供的别人的文章，想看设计代码的话，可以看我的设计代码，良心推荐！

总结

二叉树的知识点还是挺复杂、多样的。作者也是入门级别水平，要学的内容还是挺多的，尽可能的将自己理解的内容通过博客的方式写出来，帮助自己也拉别人一把。