二叉树的5个重要性质「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

1.在二叉树的第i层上最多有2 ^i-1 个节点 。（i>=1）

 用归纳法证明：

归纳基：i = 1 层时，只有一个根结点，
                    2i-1 = 20 = 1；

归纳假设：假设i=k时，命题成立;

归纳证明：二叉树上每个结点至多有两棵子树，则
第 k+1 层的结点数 最多为2k-1 x 2 = 2k+1-1 。

2.二叉树中如果深度为k,那么最多有2^k-1个节点。(k>=1）

 证明：

基于性质1，深度为 k 的二叉树上的结点数至多为
       2^0+2^1+ …..+2^k -1 = 2^k -1 

3.n₀=n₂+1  n₀表示度数为0的节点 n₂表示度数为2的节点

    推导过程 根据两个公式

    1. n=n₀+n₁+n₂    n表示二叉树中的节点总个数,n₁表示度数为1的节点个数

    2.n-1=2n₂+n₁      通过观察二叉树我们可知，除了根节点之外，其余的任何节点都有一个入口分支，其他节点都有一个入口分支，那么节点的总分支数等于节点个数减一，度数为2的节点有2个出口分支，度数为一的有1个出口分支，度数为0的节点没有出口分支 所以总的分支个数为 2n₂+n₁

4.在完全二叉树中，具有n个节点的完全二叉树的深度为[log₂n]+1，其中[log₂n]+1是向下取整。

     推导过程根据性质 2: 假设深度为k 的满二叉树的节点个数一定为2^k-1，那么n=2^k-1推得满二叉树的度数为k=log₂(n+1);

 完全二叉树是具有n个节点的二叉树，若按层序编号那么其编号与同样深度的满二叉树的节点编号在二叉树的位置相同，那么他就是完全二叉树，也就是说他的叶子几点只可能出现在最下边的两层，他的深度等于满二叉的深度，但他的节点一定少于等于满二叉树的节点个数，但一定多与2^k-1-1,2^k-1-1第度数为k-1层的满二叉树的节点个数，那么n就满足2^k-1-1<n<=2^k-1,由于n为整数那么n<=2^k-1可以推出n<=2^k ,n>2^k-1-1可以推出 n>=2^k-1,所以2^k-1<n<=2^k  ,即可得k-1<=log₂n<k 而k作为整数因此k=[log₂n]+1

设 完全二叉树的深度为 k 

则根据第二条性质得 2k-1 -1<n ≤ 2k -1,即2k-1≤  n < 2k      即   k-1 ≤  log2 n < k 

因为 k 只能是整数，因此， k =[log2n] + 1

5.若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：

(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;  

(2) 若 2i>n，则该结点无左孩子，  否则，编号为 2i 的结点为其左孩子结点；

(3) 若 2i+1>n，则该结点无右孩子结点，  否则，编号为2i+1 的结点为其右孩子结点。