……
一、树的基本概念
树（Tree）有节点、根节点、父节点、子节点、兄弟节点。
一棵树可以没有任何节点，称为空树。
一棵树可以只有1个节点，也就是只有根节点。
每个节点下的树称为子树，二叉树有左子树和右子树。
如图：
- 1是根节点
- 2的父节点是1
- 1的子节点是2、3、4、5、6
- 21和22的父节点都是2，21和22是兄弟节点（22和31不是兄弟节点）
节点的度（degree）：子树的个数（例：上图中节点2的度是2，节点3的度是1）。
树的度：所有节点度中的最大值（例：上图中子树最多的是根节点1的子节点，所以树的度是5）。
叶子节点（leaf）：度为 0 的节点（例：上图中的4、21、221等节点）。
非叶子节点：度不为 0 的节点（例：上图中的22、5等节点）。
层数（level）：根节点在第 1 层，根节点的子节点在第 2 层，以此类推（有些资料也从第 0 层开始计算）（例：上图中节点22的层数是3，节点5的层数是2）。
节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数（例：上图中节点51的深度是3）。
节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数（例：上图中节点2的高度是3）。
树的深度：所有节点深度中的最大值（例：上图中节点深度最大值是节点221，深度是4）。
树的高度：所有节点高度中的最大值（例：上图中节点高度最大值是节点1，高度是4）。
有序树：树中任意节点的子节点之间有顺序关系。
无序树：树中任意节点的子节点之间没有顺序关系，也称为“自由树”。
森林：由m（m ≥ 0）棵互不相交的树组成的集合。
树的深度等于树的高度。
二、二叉树
2.1. 二叉树的特点
- 每个节点的度最大为 2（最多拥有 2 棵子树），最小为0
- 左子树和右子树是有顺序的
- 即使某节点只有一棵子树，也要区分左右子树
疑问：二叉树是有序树还是无序树？有序树。
2.2. 二叉树的性质
非空二叉树的第
i层，最多有2^(i − 1)个节点（ i ≥ 1 ）。在高度为
h的二叉树上最多有2^h − 1个结点（ h ≥ 1 ）。对于任何一棵非空二叉树，如果叶子节点个数为
n0，度为 2 的节点个数为n2，则有:n0 = n2 + 1。- 假设度为 1 的节点个数为
n1，那么二叉树的节点总数n = n0 + n1 + n2 - 二叉树的边数
T = n1 + 2 * n2，除了根节点的其他节点头部都有一条边，所以边数也可以是总节点数减去根节点，即T = n - 1。所以T = n1 + 2 * n2 = n0 + n1 + n2 – 1 - 因此
n0 = n2 + 1
- 假设度为 1 的节点个数为
2.3. 真二叉树（Proper Binary Tree）
真二叉树：所有节点的度都要么为 0，要么为 2。换句话：所有非叶子节点的度都为 2。
2.4. 满二叉树（Full Binary Tree）
满二叉树：最后一层节点的度都为 0，其他节点的度都为 2。换句话：所有非叶子节点的度都为 2，且所有的叶子节点都在最后一层
在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多。
满二叉树一定是真二叉树，真二叉树不一定是满二叉树。
假设满二叉树的高度为h（ h ≥ 1 ），那么：
- 第 i 层的节点数量：
2^(i − 1) - 叶子节点（第h层）数量：
2^(h − 1) - 总节点数量：
n = 2^h − 1 = 2^0 + 2^1 + 2^2 + ⋯ + 2^(h−1) - 高度：
h = log2(n+1)
2.5. 完全二叉树（Complete Binary Tree）
完全二叉树：对节点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应。叶子节点只会出现最后 2 层，最后 1 层的叶子结点都靠左对齐。并且从根结点至倒数第 2 层是一棵满二叉树。
满二叉树：
完全二叉树：
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
2.5.1. 完全二叉树的性质
度为 1 的节点只有左子树（因为左对齐）
度为 1 的节点要么是 1 个，要么是 0 个（因为从上至下，从左至右原则）
同样节点数量的二叉树，完全二叉树的高度最小（因为从上至下，从左至右原则）
假设完全二叉树的高度为
h（ h ≥ 1 ），那么：- 至少有
2^0 + 2^1 + 2^2 + ⋯ + 2^(h−2) + 1 = 2^(h − 1)个节点 - 最多有
2^0 + 2^1 + 2^2 + ⋯ + 2^(h−1)= 2^h − 1个节点（满二叉树） - 总节点数量为
n:2^(h − 1) ≤ n < 2^hh − 1 ≤ log2n < hh = floor(log2n) + 1
- 至少有
一棵有
n个节点的完全二叉树（n > 0），从上到下、从左到右对节点从1开始进行编号，对任意第i个节点：- 如果
i = 1，它是根节点 - 如果
i > 1，它的父节点编号为floor(i / 2) - 如果
2i ≤ n，它的左子节点编号为2i - 如果
2i > n，它无左子节点 - 如果
2i + 1 ≤ n，它的右子节点编号为2i + 1 - 如果
2i + 1 > n，它无右子节点
- 如果
一棵有
n个节点的完全二叉树（n > 0），从上到下、从左到右对节点从0开始进行编号，对任意第i个节点：- 如果
i = 0，它是根节点 - 如果
i > 0，它的父节点编号为floor((i – 1) / 2) - 如果
2i + 1 ≤ n – 1，它的左子节点编号为2i + 1 - 如果
2i + 1 > n – 1，它无左子节点 - 如果
2i + 2 ≤ n – 1，它的右子节点编号为2i + 2 - 如果
2i + 2 > n – 1，它无右子节点
- 如果
2.5.2. 完全二叉树的面试题
题目： 如果一棵完全二叉树有 768 个节点，求叶子节点的个数。
解答：
假设叶子节点个数为 n0，度为 1 的节点个数为 n1，度为 2 的节点个数为 n2。
- 总结点个数
n = n0 + n1 + n2， - 由于
n0 = n2 + 1，所以n = 2n0 + n1 – 1。
由于完全二叉树的 n1 要么为 0，要么为 1。所以：
- n1为1时，
n = 2n0，n 必然是偶数- 叶子节点个数
n0 = n / 2，非叶子节点个数n1 + n2 = n / 2
- 叶子节点个数
- n1为0时，
n = 2n0 – 1，n 必然是奇数- 叶子节点个数
n0 = (n + 1) / 2，非叶子节点个数n1 + n2 = (n – 1) / 2
- 叶子节点个数
综上得出：
- 叶子节点个数
n0 = floor( (n + 1) / 2 ) = ceiling( n / 2 )，编程时由于n0和n是int类型，可以这样写：n0 = (n + 1) >> 1 - 非叶子节点个数
n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 ) - 因此叶子节点个数为 384