书节上回，我们继续谈论二叉树、N叉树以及树的存储结构。

01 、满二叉树

如果一棵二叉树，除最后一层节点外，每一层的节点数都达到最大值，即每个节点都有两个子节点，同时所有叶子节点都在最后一层，则这个二叉树为满二叉树。

因此，满二叉树具有以下特性：

（1）树的最大层数为k(k≥0，即层数从0开始)，则第i层的节点总数为2 ⁱ ，树的叶子节点总数为2 ^k ，树的总节点数为2^(k+1) - 1；

（2）如果已知树的总节点数为n，则树的最大层数为k=log2(n+1) - 1(k≥0，即层数从0开始)；

（3）从树的顶层开始从上到下，从左到右，对每个节点按顺序进行编号，根节点为1作为起始点；

a.对于节点i，如果其存在父节点，则父节点编号为i/2向下取整；

b.对于节点i，如果其存在左节点则左节点编号为2i，如果其存在右节点则右节点编号为2i+1；

02 、完全二叉树

如果一棵树，叶子节点只能出现在最后两层，并且最后一层的节点都集中在左侧且从左到右是连续的。

由此我们可以得到完全二叉树具有以下特性：

（1）叶子节点只能出现在倒数第一层和倒数第二层；

（2）倒数第一层的所有叶子节点都集中于此层最左侧连续位置；

（3）倒数第二层如果存在叶子节点则层的所有叶子节点都集中在此层最右侧连续位置；

（4）所有节点中如果存在一个节点只有一个子节点，则此节点一定在倒数第二层，并且这个子节点一定是左节点；

（5）满二叉树是完全二叉树的特例；

（6）满二叉树的特性（3）也适用于完全二叉树；

（7）如果完全二叉树不是满二叉树，则除最后一层外为满二叉树，适用满二叉树所有性质；

（8）如果节点总数为n，并且i≤n/2，则第i个节点为非叶子节点；

（9）如果节点总数为n，如果n为偶数则叶子节点数为n/2；如果n为奇数则叶子节点数为(n+1)/2；

（10）如果树的层数为k(k≥0)，则树的总节点数的范围为[2 ^k , 2 ^(k+1) - 1)]；

（11）如果已知树的总节点数为n，则树的最大层数为k=log2(n+1) (k≥0，即层数从0开始)，并且k向下取整；

03 、二叉搜索树

二叉搜索树是一种特殊的二叉树，又称二叉查找树或二叉排序树，可以说这是一种为了查询而生的二叉树。

二叉搜索树具有以下性质：

（1）每个节点值必须唯一，不能有重复值；

（2）每个节点最多有两个子节点；

（3）对于任意一个节点，如果其存在左子树，则左子树上所有节点值小于该节点值，如果其存在右子树，则右子树上所有节点值大于该节点值；

（4）左子树和右子树本身也各自是二叉搜索树；

04 、平衡二叉树

平衡二叉树的意义在于使二叉树在某种状态下保持平衡，即树中任意一个节点的左右子树高度差的绝对值小于等于1，并且其左右子树同样也是平衡二叉树。

平衡二叉树是通过控制树的深度来优化二叉搜索树的平均操作时间。

AVL树是平衡二叉树的一种特例，严格遵循平衡二叉树的定义，也是最早发明的自平衡二叉搜索树。

红黑树也是一种自平衡二叉搜索树，但其没有严格遵循平衡二叉树的定义，平衡条件相对较宽松，允许左右子树高度差的绝对值大于1。

这两种树我们后面会找机会单独详细讲解。

此外还有哈夫曼树、线段树、伸展树、替罪羊树等多种二叉树，这里就不一一介绍了，后面我们单独拿出来讲解。

05 、N叉树

B树、B+树、2-3-4树、R树、Trie树等多叉树，我们后面会找机会单独详细讲解。

06 、存储结构

1、顺序存储

顺序存储只用一组连续的地址空间来存储整个树。

并不是所有树都适合顺序存储的，还记得上面所提到的满二叉树的特性（3）吗？如果把满二叉树从上到下、从左到右，则左右子节点编号可以通过父节点编号表示。如果父节点编号为i，则其左子节点编号为2i，其右子节点编号为2i+1。而根节点作为已知起始值1，就意味着其后代节点都可以通过根节点直接或间接表示。

编号不经让我们想到数组下标，这就意味着我们可以把整个满二叉树装进数组里。因为完全二叉树也满足满二叉树的特性（3），所以完全二叉树也可以装进数组。如下图所示。

那如果非完全二叉树呢？能否放入数组中呢? 答案是肯定可以。我们只需要把非完全二叉树想象成满二叉树，把缺少的节点虚拟补全，然后对其编号，最后装入数组，如下图：

但是我们会发现编号4、5、7位都为空值。即使如此，还是很浪费数组空间的，因此顺序存储是比较适合完全二叉树存储的，而其他类型二叉树并不是很适合。

2、链式存储

顺序存储有其局限性，因此大多数树都是使用链式存储。链式存储的核心思想就是每一个节点设计为两部分，其一为数据域存放元素值，其二为指针域存放指向子节点指针，节点有多少个子节点指针域就有多少个指针。

我们还是以二叉树为例，链式存储结构如下：

注 ：测试方法代码以及示例源码都已经上传至代码库，有兴趣的可以看看。https://gitee.com/hugogoos/Plan+er