数据结构与算法：二叉树（Binary Tree）

树（Tree）结构应该算得上是数据结构中非常重要的一种了，

它被广泛应用于数据的底层存储，像集合类Set、Map用到了红黑树、数据库索引使用了平衡树。

今天我们来探索树（Tree）的入门类型：二叉树（Binary Tree）

01

初识

就像认识人一样，我们先看一下二叉树的"五官"

• 层：从根节点算起，1起始，向下累加
• 节点：图中每一个单位叫做一个节点，最上层的叫做根节点，没有子节点的叫做叶子节点。
• 深度：从根节点算起，0起始，向下累加
• 高度：从底层算起，0起始，向上累加
• 二叉：所谓二叉树，即每个节点下层最多有两个子节点。

在了解了基本概念之后，我们来认识一下不同类型的"二叉树"

02

满二叉树

通过这个对比应该很好理解，满二叉树，即叶子节点都在最底层，且除叶子节点外，每个节点的子节点都是两个，也就是子节点是满的。

03

完全二叉树

依然通过对比来感受一下

相比于满二叉树，完全二叉树难理解一些，所以这里举了多个例子对比。

总结一下完全二叉树的特点：

• 除最下层以外，上层是一个满二叉树
• 最下层的叶子节点从右侧向左看起，没有空缺节点

细品一下其实满二叉树属于特殊的完全二叉树。

在了解了基本的二叉树之后，我们来深入探寻一下二叉树的实现方式：

04

基于链表：链式存储

链表回顾

数据结构与算法--链表（Linked list）

链表的每个节点分别存有指向左右子节点的指针，这样我们就可以顺着指针找到二叉树的所有数据。

05

基于数组：顺序存储

数组实现二叉树的思路是：通过计算公式，将二叉树的所有节点转换成数组下标，并按顺序存储。

数组回顾

数据结构与算法--数组（Array）

我们试着摸索一下这个计算公式：

可以看到，我将二叉树做编号对应成了数组的下标，为了方便计算通常从数组下标为1的位置开始存放。

如果我们的当前节点在根节点1，那么左侧的子节点就是：2 * 1 = 2

右侧子节点就是：2 * 1 + 1 = 3

由此可以推出计算公式：

• 当前节点下标：i
• 左侧子节点下标：2 * i
• 右侧子节点下标：2 * i + 1

这样一来就轻松的实现了数组方式存储二叉树。

相比于链式存储，以数组方式存储二叉树更为节省内存，因为链式存储需要额外开辟内存来存放指向左右子节点的指针。

06

回看完全二叉树

我将顺序存储的图片再贴一次：

你应该不难发现这是一个完全二叉树，在使用完全二叉树作顺序存储时，数组只浪费了一块内存，也就是下标0。

如果是非完全二叉树呢？

显而易见，非完全二叉树无法更好的利用数组的空间，会造成空间浪费。

所以完全二叉树最适合使用顺序存储。

今天我们了解了不同类型的二叉树以及二叉树的实现方式，下一期我们来继续探索二叉树的增删改查。