二叉树的基本概念
定义：二叉树（binary tree）是一棵 度为二 的树，其孩子有左右之分，也分别都是二叉树。(度绝对不可以超过 2，且是一个有序树)
二叉树的重要性质
性质一: 在二叉树的第 i 层上最多有 2^(i-1)个结点（i≥1）。
性质二: 深度为 k 的二叉树最多有 2^k- 1 个结点（k≥1）。
性质三: 对任一二叉树，叶子结点数为 X，度为 2 的结点数为 Y，则 X =Y+1。
衍生出两类二叉树
- 满二叉树（full binary tree）：一棵深度为 k 且有 2^k- 1 个结点的二叉树称为满二叉树。
- 完全二叉树（complete binary tree）：一棵深度为 k 的满二叉树的第 k 层的右边几个结点不存在则为完全二叉树。
完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质:
性质四:n 个结点的完全二叉树的深度为 ⌊log2 n⌋+1。
性质五: 对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i，完全二叉树还有以下 3 个结论成立：
- 当 i>1 时，父亲结点为结点 [i/2]。（i=1 时，表示的是根结点，无父亲结点）
- 如果 2×i>n（总结点的个数），则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2×i。
- 如果 2×i+1>n，则结点 i 肯定没有右孩子；否则右孩子是结点 2×i+1