二叉树的性质
性质 1
在二叉树的第 i层 上至多有 2^(i-1)个结点。
性质 2
深度为 k 的二叉树最多有 2^k - 1 个结点。
性质 3
对任意二叉树 T，如果度数为 0 结点数为 n0，度数为 1 结点数为 n1，度数为 2 结点数为 n2，则 n0 = n2 + 1。
推导：
- 二叉树 T 的结点总数 n = n0 + n1 + n2
- 二叉树的分支结点总数 B = n - 1
- 由于分支结点是由度为 1 和度为 2 的结点生成的，即分支结点总数 B = n1 + 2 * n2
- 因此 n - 1 = n1 + 2 * n2，代入 n = n0 + n1 + n2 可得 n0 = n2 + 1
性质 4
具有 n 个结点的完全二叉树的深度为 floor(log2 n) + 1。
性质 5
对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
- 若 i = 1，则该结点是二叉树的根，无双亲；否则，编号为 floor(i/2) 的结点为其双亲结点。
- 若 2i > n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点。
- 若 2i + 1 > n，则该结点无右孩子结点；否则，编号为 2i + 1 的结点为其右孩子结点。
这里索引是从 1 开始的，如果根节点索引是 0（如在数组中实现），则一个 i 节点的左右孩子为 2i + 1 和 2i + 2。
链接到
- 上一个知识点：6.3 二叉树的基本概念
- 下一个知识点：6.5 二叉树的存储结构