总结 | 二叉树的性质

二叉树的性质1

• 在二叉树的第i层上至多有2的
  i-1次方个结点（i>=1）

• 理解：观察如下图：
  第一层（i=1）有1个：2^1-1=1
  第二层（i=2）有2个：2^2-1=2
  第三层（i=3）有4个：2^3-1=4

  
  image.png

二叉树的性质2

• 深度为k的二叉树至多有2的k次方-1个结点（k>=1）

• 理解：如下图所示二叉树的深度为3：
  结点数：(2^3)-1=7

  
  image.png

二叉树的性质3

• 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

• 理解：终端结点数其实就是叶子结点数，而一棵二叉树，除了叶子结点外，剩下的就是度为1或为2的结点数了，假设n1为度为1的结点数，则树T的结点数n=n0+n1+n2。
  如下图：
  度为0的结点是：4，5，6（3个）
  度为1的结点是：3（1个）
  度为2的结点是：1，2（2个）
  6=3+1+2
  再换一个角度思考：数一数它的连线数，根结点只有分支出去，没有分支进入，所以分支线的总数为结点总数-1，如图：一共有5个分支，6个结点，对于1，2来说，连线数=2*2，对于3来说连线数=1*1
  总连线数=n-1=n2*2+n1
  n=n2*2+n1+1=n0+n1+n2
  =>n0=n2+1

  
  image.png

二叉树的性质4

• 具有n个结点的完全二叉树的深度为[log2n]+1（[x]表示不大于x的最大整数）

• 理解：由满二叉树的定义我们可以知道，深度为k的满二叉树的结点数n一定是（2^k）-1，因为这是最多的结点个数，那么对于n=（2^k)-1推到得到的满二叉树的深度为k=log2（n+1），比如结点数为15的满二叉树，深度为4

• 完全二叉树是一棵具有n个结点的二叉树，若按层数编号后其编号与同样深度的满二叉树中编号结点在二叉树中位置完全相同，那他就是完全二叉树，也就是说，它的叶子节点只会出现在最下面两层。它的结点数一定少于等于同样深度的满二叉树的结点数(2^{k)-1,但一定多于（2}k-1）-1，即满足：
  

  image.png
  由于结点数n是整数，所以：
  image.png
  两边取对数，得到：
  image.png
  而k作为深度也是整数，因此k=[log2n]+1
  image.png