# 二叉树
# 概念
如果树中每个节点最多只能有两个子节点，这样的树就称为"二叉树"。
二叉树可以为空，也就是没有节点
若不为空，则他由根节点和左子树（TL）和右子树（TR）两个不相交的二叉树组成。
# 二叉树的五种形态
# 二叉树的特性
- 一个二叉树第 i 层最大的节点数为
2^(i-1) i ≥ 1 - 深度为 k 的二叉树有最大节点总数为
2^k-1 k ≥ 1 - 对任何非空二叉树 T ，若 n0 表示叶子节点的个数，n2 是度为2的非叶子节点个数，那么两者满足关系 n0 = n2 + 1
# 完美二叉树
完美二叉树也称为满二叉树，除了最下一层的叶子节点外，每层节点都有2个子节点。
# 完全二叉树
除二叉树最后一层外，其他各层的节点数都达到最大个数。
且最后一层从左向右的叶节点连续存在，只缺右侧若干节点。
完美二叉树是特殊的完全二叉树。
下面的不是完全二叉树，因为D节点还没有右节点，但是E节点有了左右节点。
# 二叉树的存储
二叉树的存储常见的方式是数组和链表
使用数组
完全二叉树：从上至下，从左到右顺序存储
非完全二叉树要转成完全二叉树才可以按照上面的方案存储。但是会造成很大的空间浪费
使用链表
二叉树最常见的方式还是使用链表存储。
每个节点封装成一个 Node, Node中包含存储的数据，左节点的引用，右节点的引用
