树的相关知识点

---

一.

1.结点n=0，称为空树

二. 二叉树的性质（树的深度从1开始计数）

1、 第i层至多有2^（i-1）个结点

2、 深度为k的二叉树至多有（2^k）-1个结点

3、对任意二叉树的n个结点：叶子结点n0，度为1的结点n1，度为2的结点n2，分支总数B

* n=n0+n1+n2
  n=B+1
  B=n1+2n2
* n=n1+2n2+1

• 综合上式有：n0=n2+1

4、满二叉树：深度为k且含有结点数为（2^k）-1的二叉树

5、完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中 编号从1至n一一对应时，称为完全二叉树

特点：
    1）叶子结点只可能在层次最大的两层出现
    2）对任一结点，若其右分支下的子孙最大层次为l，则其左分支下的子孙的最大层次必为l或l+1

####6、具有n个结点的完全二叉树的深度为log2（N）+1，log2（N）取下界