满二叉树与完全二叉树的概念及其二叉树的存储

什么是满二叉树呢？
一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。

image.png
什么是完全二叉树呢？
完全二叉树的条件没有满二叉树那么苛刻：满二叉树要求所有分支都是满的；而完全二叉树只需保证最后一个节点之前的节点都齐全即可。
image.png

二叉树的存储

二叉树属于逻辑结构，它可以通过多种物理结构来表达。
二叉树可以用哪些物理存储结构来表达呢？
1. 链式存储结构。
链表是一对一的存储方式，每一个链表节点拥有data变量和一个指向下一节点的next指针。
而二叉树稍微复杂一些，一个节点最多可以指向左右两个孩子节点，所以二叉
树的每一个节点包含3部分。
存储数据的data变量
指向左孩子的left指针
指向右孩子的right指针

image.png
2. 数组。
使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来。
为什么这样设计呢？因为这样可以更方便地在数组中定位二叉树的孩子节点和父节点。
假设一个父节点的下标是parent，那么它的左孩子节点下标就是2×parent +1；右孩子节点下标就是2×parent + 2。
反过来，假设一个左孩子节点的下标是leftChild，那么它的父节点下标就是（leftChild-1）/ 2。
假如节点4在数组中的下标是3，节点4是节点2的左孩子，节点2的下标可以直接通过计算得出。
节点2的下标 = (3-1)/2 = 1
image.png
显然，对于一个稀疏的二叉树来说，用数组表示法是非常浪费空间的。
什么样的二叉树最适合用数组表示呢？
二叉堆，一种特殊的完全二叉树，就是用数组来存储的。