（一）树与二叉树

我们将 现实生活中的树，倒过来看， 可以构成树； 树上的每个元素可以看成节点；
节点与节点之间的关系， 上下节点间 作为 父子节点， 左右节点之间作为兄弟节点；

根节点： 将没有父节点的节点称为 根节点；叶子节点： 将没有子节点的 节点称为 叶子节点；

树中 比较相似 却又不同的三个 概念： 高度height， 深度depth ， 层level；
高度： 从该节点往下看；
深度： 从该节点往上看；

节点的高度 = 节点到叶子节点的最长路径长度（边数）节点的深度 = 根节点 到 这个节点的路径长度（边数）节点的层 = 节点的深度 + 1树的高度 = 根节点的高度树的深度 = 0

此外，还有一种 定义 节点的度；

节点的度 = 该节点孩子的个数树的 度 = 便是指 所有节点中，节点度的最大值； 即该节点有最多的孩子； 2. 二叉树

对于二叉树， 便是指 每个节点最多只有两个叉；
常见的二叉树， 有满二叉树 和 完全二叉树；

满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

满二叉树的条件：

所有的叶子节点 都在最底层；除了叶子节点外， 所有节点都有左右子节点；

完全二叉树的满足条件：

叶子节点只分布在最底层 和 倒数第二层；最底层的叶子节点，都会靠左排列；

那么为什么完全二叉树，最底层叶子节点都要靠左排列呢？
为什么没有靠右排列呢？

这便是涉及到 完全二叉树的 存储方式 – 数组存储；

二叉树的 存储方式 可以分为 链式存储 ， 和顺序存储；

那么什么样的二叉树 适合用 链式存储， 什么类型的二叉树 又适合 顺序存储呢？

以及为什么适合各自的存储类型呢？

每个节点，包含三个部分：
数据本身， 以及指向 左右子节点的 两个指针；
从根节点开始，通过左右子节点， 将整个树串起来；

如果当前点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2， 其父节点便是 i/2;

而在实践中， 存储时， 下标0空出，用于占位。 下标i 从1 开始，这样左孩子节点 便是 2i, 右孩子节点是 2i + 1;

回答上述， 什么样的二叉树 适合用 链式存储， 什么类型的二叉树 又适合 顺序存储呢？
以及为什么适合各自的存储类型呢？

对于非完全二叉树， 一般使用 链式存储；

对于完全二叉树， 使用 数组存储， 因为此时省去了记录 左右子节点的指针， 从而节省空间；

因为完全二叉树的采用 数组存储的方式， 这也是完全二叉树 为什么要定义成，最底层的叶子节点 要靠左排列；