树是经常用到的数据结构，用来模拟具有树状结构性质的数据集合。
从图的观点来看，树可视为拥有N个节点和N-1条边的一个有向无环图
**二叉树**（Binary Tree）是一种更为典型的树状结构，二叉树是每个节点最多有两个子树的树结构，通常子树被称为左子树、右子树
对于二叉树，需要掌握常见的排序、遍历算法。

二叉树遍历：

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

斜树

左斜树

右斜树

满二叉树

**Full Binary Tree**
如果一个二叉树的层数为**K**，且结点总数是**2****k**** -1** ，则它就是满二叉树。
满二叉树特点（高度 h）：

• 叶子节点都在最后一层
• 只有度为0、度为2的节点
• 叶子数是：**2****h****　**　
• 第 k 层的结点数是： **n = 2****(k - 1)**
• 总结点数：**n = 2****k**** - 1**，（反过来，高度 **h = log****2****(n+1)**)

完全二叉树

**Complete Binary Tree**
完全二叉树的节点数是任意的，从形式上讲它是个缺失的的三角形，但所缺失的部分一定是右下角某个连续的部 分，最后那一行可能不是完整的
对于k层的完全二叉树，节点数的范围2^ (k - 1) -1 < N< 2^k - 1；设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边， 这就是完全二叉树。
个人所想：层序遍历上满足节点连续性。
完全二叉树特点（高度 h，共n个节点）：

• 高度 **h = log****2****(n+1)**