二叉树的性质
由于二叉树结构特殊，我们可以总结出以下的五个性质：
性质一：对于一棵二叉树，第i层的最大结点数量为 2i−1 个，比如二叉树的第一层只有一个根结点，也就是 20 = 1 ，而二叉树的第三层可以有 22 = 4个结点。
性质二：对于一棵深度为k的二叉树，可以具有的最大结点数量为： n = 20 + 21 + 22 + . . . + 2k − 1 我们发现，实际上每一层的结点数量，组成了一个等比数列，公比q为2，结合等比数列求和公式，我们可以将其简化为：
所以一棵深度为k的二叉树最大结点数量为 n = 2k − 1 ，顺便得出，结点的边数为 E = n − 1 。性质三：假设一棵二叉树中度为0、1、2的结点数量分别为 n0、 n1、 n2，由于一棵二叉树中只有这三种类型的结点，那么可以直接得到结点总数： n = n0+n1+n2 我们不妨换一个思路，我们从二叉树的边数上考虑，因为每个结点有且仅有一条边与其父结点相连，那么边数之和就可以表示为： E = n1+2n2 度为1的结点有一条边，度为2的结点有两条边，度为0的结点没有，加在一起就是整棵二叉树的边数之和，结合我们在性质二中推导的结果，可以得到另一种计算结点总数的方式： E = n−1=n1+2n2 n = n1+2n2+1
再结合我们第一个公式： n = n0+n1+n2=n1+2n2+1 综上，对于任何一棵二叉树，如果其叶子结点个数为 n 0 n_0 n0 ，度为2的结点个数为 n 2 n_2 n2 ，那么两者满足以下公式： n0 = n2+1 （性质三的推导过程比较复杂，如果觉得麻烦推荐直接记忆）
性质四：完全二叉树除了最后一层有空缺外，其他层数都是饱满的，假设这棵二叉树为满二叉树，那么根据我们前面得到的性质，假设层数为k，那么结点数量为：n=2k−1 ，根据完全二叉树的性质，最后一层可以满可以不满，那么一棵完全二叉树结点数n满足： 2k−1−1 < n <= 2k−1 因为n肯定是一个整数，那么可以写为： 2k−1 <= n <= 2k−1 现在我们只看左边的不等式，我们对不等式两边同时取对数，得到： k−1 <= log2 n
综上所述，一棵具有n个结点的完全二叉树深度为 k=⌊log2 n⌋ + 1 。
（性质四的推导过程比较复杂，如果觉得麻烦推荐直接记忆）
性质五：一颗有n个结点的完全二叉树，由性质四得到深度为 k=⌊log2 n⌋+1 现在对于任意一个结点i，结点的顺序为从上往下，从左往右：
对于一个拥有左右孩子的结点来说，其左孩子为2i，右孩子为2i + 1。
如果i = 1，那么此结点为二叉树的根结点，如果i > 1，那么其父结点就是 ⌊ i / 2 ⌋ \lfloor i/2 \rfloor ⌊i/2⌋，比如第3个结点的父结点为第1个节点，也就是根结点。
如果2i > n，则结点i没有左孩子，比如下面图中的二叉树，n为5，假设此时i = 3，那么2i = 6 > n = 5 说明第三个结点没有左子树。
如果2i + 1 > n，则结点i没有右孩子。
标签：结点,数学,二叉树,一棵,n1,2i,性质 From： https://www.cnblogs.com/Ragnaros-Y/p/17142891.html