数据结构与算法二叉树（BinaryTree）

　　树（Tree）结构应该算得上是数据结构中非常重要的一种了，
　　它被广泛应用于数据的底层存储，像集合类Set、Map用到了红黑树、数据库索引使用了平衡树。
　　今天我们来探索树（Tree）的入门类型：二叉树（Binary Tree）
　　初识
　　就像认识人一样，我们先看一下二叉树的＂五官＂
　　层：从根节点算起，1起始，向下累加 节点：图中每一个单位叫做一个节点，最上层的叫做根节点，没有子节点的叫做叶子节点。 深度：从根节点算起，0起始，向下累加 高度：从底层算起，0起始，向上累加 二叉：所谓二叉树，即每个节点下层最多有两个子节点。
　　在了解了基本概念之后，我们来认识一下不同类型的＂二叉树＂
　　满二叉树
　　通过这个对比应该很好理解，满二叉树，即叶子节点都在最底层，且除叶子节点外，每个节点的子节点都是两个，也就是子节点是满的。
　　完全二叉树
　　依然通过对比来感受一下
　　相比于满二叉树，完全二叉树难理解一些，所以这里举了多个例子对比。
　　总结一下完全二叉树的特点： 除最下层以外，上层是一个满二叉树 最下层的叶子节点从右侧向左看起，没有空缺节点
　　细品一下其实满二叉树属于特殊的完全二叉树。
　　在了解了基本的二叉树之后，我们来深入探寻一下二叉树的实现方式：
　　基于链表：链式存储
　　关于链表回顾：
　　数据结构与算法--链表（Linked list）
　　链表的每个节点分别存有指向左右子节点的指针，这样我们就可以顺着指针找到二叉树的所有数据。
　　基于数组：顺序存储
　　数组实现二叉树的思路是：通过计算公式，将二叉树的所有节点转换成数组下标，并按顺序存储。
　　我们试着摸索一下这个计算公式：
　　可以看到，我将二叉树做编号对应成了数组的下标，为了方便计算通常从数组下标为1的位置开始存放。
　　如果我们的当前节点在根节点1，那么左侧的子节点就是：2 * 1 = 2
　　右侧子节点就是：2 * 1 + 1 = 3
　　由此可以推出计算公式： 当前节点下标：i 左侧子节点下标：2 * i 右侧子节点下标：2 * i + 1
　　这样一来就轻松的实现了数组方式存储二叉树。
　　相比于链式存储，以数组方式存储二叉树更为节省内存，因为链式存储需要额外开辟内存来存放指向左右子节点的指针。
　　回看完全二叉树
　　我将顺序存储的图片再贴一次：
　　你应该不难发现这是一个完全二叉树，在使用完全二叉树作顺序存储时，数组只浪费了一块内存，也就是下标0。
　　如果是非完全二叉树呢？
　　显而易见，非完全二叉树无法更好的利用数组的空间，会造成空间浪费。
　　所以完全二叉树最适合使用顺序存储。
　　今天我们了解了不同类型的二叉树以及二叉树的实现方式，下一期我们来继续探索二叉树的增删改查。