39-二叉树的性质总结

1. 性质1

性质1：非空二叉树上叶子节点数等于双分支节点数加1。

  1. 假设二叉树上叶子节点数用n0$n_0$表示，单分支节点数用n1$n_1$表示，双分支节点数用n2$n_2$表示，则总的节点数n=n0+n1+n2$n=n_0+n_1+n_2$

  我们仔细观察上图就能发现，二叉树中，叶子节点总共有4个（D，E，F，H），单分支节点数1个（G），双分支节点数总共3个（A，B，C）。因此我们可以得出二叉树中总的节点数=4+1+3=8$总的节点数=4+1+3=8$。


  2. 在一棵二叉树中总的分支数（即度数）等于单分支节点数加上双分支节点数的2倍。即总的分支数=n1+2n2$总的分支数=n_1+2n_2$。我们可以根据第一点推出第二点的：二叉树总的分支数=1+2×3=7$总的分支数=1+2\times 3=7$。


  3. 由于二叉树中除根节点以外，每个节点都有唯一的一个分支指向它，因此二叉树中有：总的分支数 = 总结点数 - 1，即总的分支数=n0+n1+n2−1$总的分支数=n_0+n_1+n_2-1$

  因此再结合第二点可以得出：n0+n1+n2−1=n1+2n2$n_0+n_1+n_2-1=n_1+2n_2$

  消项后：n0=n2−1$n_0=n_2-1$

2. 性质2

性质2：非空二叉树上第i层上至多有2i−1$2^{i-1}$个节点（其中i≥1$i\ge 1$）。

关于性质2，大家可以仔细观察一下上图。
在第一层中只有根节点A，套用上面的公式得出21−1=20=1$2^{1-1}=2^0=1$

在第二层中有B和C节点，继续套用上面的公式得出22−1=21=2$2^{2-1}=2^1=2$

在第三层有D，E，F，G节点，根据上面的公式得出23−1=22=4$2^{3-1}=2^2=4$

在第四层中有H ，….. ，O节点，根据上面的公式计算出总共有8个节点。

如果有i层的话，那么通过数据归纳法可知，二叉树的第i层上至多有2i−1$2^{i-1}$个节点，且（i ≥ 1）。

3. 性质3

性质3：高度为h的二叉树至多有2h−1$2^h-1$个节点，（其中h≥1$h\ge 1$）。

通常，树的层次就是树的高度，或称为树的深度。

在只有一层的二叉树来说，根据上面的公式得出21−1=1$2^1-1=1$ ，这棵二叉树只有1个节点。

有二层的二叉树，根据上面的公式得出22−1=3$2^2-1=3$，这棵二叉树有3个节点

有三层的二叉树，根据上面的公式得出23−1=7$2^3-1=7$，这棵二叉树有7个节点

有四层的二叉树，根据上面的公式得出24−1=15$2^4-1=15$，这棵二叉树有15个节点

  对于有h层的二叉树，通过数学归纳法可以得出，此二叉树至多有2h−1$2^h-1$个节点。

  另外，当一棵二叉树高度为h，且有2h−1$2^h-1$个节点，那么这棵二叉树则又称为满二叉树，如上图中的二叉树就是一个满二叉树（仔细体会）。

4. 性质4

性质4：对完全二叉树中编号为i的节点（1≤i≤n$1\le i\le n$，n≥1$n\ge 1$，n$n$为节点数）有：

  1. 若i≤[n/2]$i\le [n/2]$，即2i≤n$2i\le n$，则编号为i的节点为分支节点，否则为叶子节点。

  假设二叉树的总结点数n为12，对于编号为4的节点来说，满足i≤[n/2]$i\le [n/2]$，所以编号为4的节点是一个分支节点。对于编号为6的节点来说，也满足i≤[n/2]$i\le [n/2]$，因此编号为6的节点也是一个分支节点；而对于编号为7的节点来说，并不满足i≤[n/2]$i\le [n/2]$，因此编号为7的节点是一个叶子节点。

  2.若n为奇数，则每个分支节点都既有左孩子节点，也有右孩子节点。

  比如在上图中的完全二叉树中在只有11个节点（n为奇数）的情况下，每个分支节点既有左孩子节点，也有右孩子节点。

  若n为偶数，则编号最大的分支节点只有左孩子节点，没有右孩子节点，其余分支节点都有左、右孩子节点。

  再比如上图中完全二叉树中有12个节点（n为偶数）， 编号最大的分支节点为F节点只有一个左孩子节点（L节点） 。而其他的分支节点（A，B，C，D，E）都有左孩子，右孩子节点。

  3. 若编号为i的节点有左孩子节点，则左孩子节点的编号为2i$2i$ 。比如对于编号为2的节点B来说，B节点的左孩子是D节点，而D节点的编号正好是4，即2i$2i$。

  若编号为i的节点有右孩子节点，则右孩子节点的编号为(2i+1)$(2i+1)$。比如对于编号为5的节点E来说，E节点的右孩子是K节点，而K节点的编号正好是11，即（2i+1）$（2i+1）$。

  4. 除树根节点外,若一个节点的编号为i，则它的双亲节点的编号为[i/2]$[i/2]$ （[x]$[x]$表示不大于x的最大整数）。

  对于根节点是没有双亲节点的，这里我们来看一下上图中的编号为9的节点，它的双亲节点就是[9/2]=4$[9/2]=4$。对于编号为8的节点来说，它的双亲节点是[8/2]=4$[8/2]=4$。

  当i为偶数时，其双亲节点的编号为(i/2)$(i/2)$，它是双亲节点的左孩子节点

  当i为奇数时，其双亲节点的编号为（i−1）/2$（i-1）/2$，它是双亲节点的右孩子节点