树的应用 —— 二叉树
二叉树（Binary Tree）是n （n ≥0）个节点构成的集合，或为空树（n =0），或为非空树。
对于非空树T ，要满足：
①有且仅有一个被称为根的节点；
②除了根节点，其余节点分为两个互不相交的子集T1和T2 ，分别被称为T 的左子树和右子树，且T1 和T2 本身都是二叉树。
二叉树是种特殊的树，它最多有两个子树，分别为左子树和右子树，二者是有序的，不可以互换。也就是说，在二叉树中不存在度大于2的节点。
【二叉树的总共5种形态】
【二叉树的性质】
[性质1：在二叉树的第 i 层上至多有2^(i -1) 个节点。]
一棵二叉树如下图所示。
由于二叉树的每个节点最多有2个孩子，第1层树根为1个节点，第2层最多为2个节点，第3层最多有4个节点，因为上一层的每个节点最多有2个孩子，因此当前层最多是上一层节点数的两倍。
数学归纳法证明：
- i =1时：只有一个根节点，2^(i -1) =2^0 =1。
- i >1时：假设第i -1层有2^(i -2) 个节点，而第i 层节点数最多是第i -1层的两倍，即第i 层节点数最多有2×2^(i -2) =2(i -1) 。
[性质2：深度为 k 的二叉树至多有2^k - 1个节点。]
证明：如果深度为k 的二叉树，每一层都达到最大节点数，如下图所示，
则把每一层的节点数加起来就是整棵二叉树的最大节点数。
[性质3：对于任何一棵二叉树，若叶子数为n0 ，度为2的节点数为n2 ，则n0 =n2 +1。]
证明：
二叉树中的节点度数不超过2，因此共有3种节点：度为0、度为1、度为2。设二叉树总的节点数为n ，度为0的节点数为n0 ，度为1的节点数为n1 ，度为2的节点数为n2 ，总节点数等于三种节点数之和，即n =n0 +n1 +n2 。
而总节点数又等于分支数b +1，即n =b +1。为什么呢？如下图所示，
从下向上看，每一个节点都对应一个分支，只有树根没有对应的分支，因此总的节点数为分支数b +1。
而分支数b 怎么计算呢？从上向下看，如下图所示，
每个度为2的节点都产生2个分支，度为1的节点产生1个分支，度为0的节点没有分支，因此分支数b =n1 +2n2 ，则n =b +1=n1 +2n2 +1。而前面已经得到n =n0 +n1 +n2 ，两式联合得：n0 =n2 +1。
[有两种特殊的二叉树：满二叉树 和 完全二叉树]
满二叉树：一棵深度为k 且有2^k -1个节点的二叉树。满二叉树的每一层都“充满”了节点，达到最大节点数，如下图所示。
完全二叉树：除了最后一层，每一层都是满的（达到最大节点数），最后一层节点是从左向右出现的。深度为k 的完全二叉树，当且仅当其每一个节点都与深度为k 的满二叉树中编号为1～n 的节点一一对应。例如，完全二叉树如下图所示，
它和上图中的满二叉树编号一一对应。完全二叉树除了最后一层，前面每一层都是满的，最后一层必须从左向右排列。也就是说，如果2没有左孩子，就不可以有右孩子，如果2没有右孩子，则3不可以有左孩子。
[性质4：具有n 个节点的完全二叉树的深度必为⌊log2n ⌋＋1。]
证明：假设完全二叉树的深度为k ，那么除了最后一层，前k -1层都是满的，最后一层最少有一个节点，如下图所示。
最后一层最多也可以充满节点，即2^(k -1) 个节点，如下图所示。
因此，2^(k -1) ≤n ≤2^k -1，右边放大后，2^(k -1) ≤n <2^k ，同时取对数，k -1≤log2n <k ，所以k =⌊log2n ⌋ +1。其中，⌊⌋表示取下限，⌊x ⌋表示小于x 的最大整数，如⌊3.6⌋=3。
例如，一棵完全二叉树有10个节点，那么该完全二叉树的深度为k=⌊log2 10⌋+1=4。
[性质5：对于完全二叉树，若从上至下、从左至右编号，则编号为i 的节点，其左孩子编号必为2i ，其右孩子编号必为2i ＋1；其双亲编号必为i /2。]
完全二叉树的编号如下图所示。
例如，一棵完全二叉树如下图所示。节点2的双亲节点为1，左孩子为4，右孩子为5；节点3的双亲节点为1，左孩子为6，右孩子为7。
【例题】
- 一棵完全二叉树有1001个节点，其中叶子节点的个数是多少？
首先找到最后一个节点1001的双亲节点，其双亲节点编号为1001/2=500，该节点是最后一个拥有孩子的节点，其后面全是叶子，即1001-500=501个叶子。
- 一棵完全二叉树第6层有8个叶子，则该完全二叉树最少有多少个节点，最多有多少个节点？
完全二叉树的叶子分布在最后一层或倒数第二层。因此该树有可能为6层或7层。
节点最少的情况（6层）：8个叶子在最后一层（即第6层），前5层是满的，如下图所示。
最少有2^5 -1+8=39个节点。
节点最多的情况（7层）：8个叶子在倒数第2层（即第6层），前6层是满的，第7层最少缺失了8×2个节点，因为第6层的8个叶子如果生成孩子的话，会有16个节点。如下图所示，最多有2^7 -1-16=111个节点。
