二叉树相关性质（更新中……）

迈不过友情╰ 2023-02-22 13:40 100阅读 0赞

## 二叉树的性质（持续更新中……） ##

1.  #### 在二叉树的`第i层`至多有`2^(i-1)`个结点（i>=1)（参考满二叉树，数学归纳法证明） ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]

1.  #### `深度为k`的二叉树至多有`2^k-1`个结点（k>=1）（`满二叉树`与`等比数列求和`） ####

> 二叉树的深度：
> 
> 1.  一颗树只有一个节点，它的深度是1；
> 2.  根节点只有左子树而没有右子树，那么二叉树的深度应该是其左子树的深度加1；
> 3.  根节点只有右子树而没有左子树，那么二叉树的深度应该是其右树的深度加1；
> 4.  根节点既有左子树又有右子树，那么二叉树的深度应该是其左右子树的深度较大值加1

利用性质1可知每层最多有`2^(k-1)`个结点，有k层。

利用等比数列求和可得=> 1+2+4+……+2^(k-1) = `2^k-1`.

> 深度为k时至少有k个结点

1.  #### 对于一个二叉树T，如果其叶子结点为`n0`，度为2 的结点数为`n2`，则`n0 = n2 + 1` ####

证明：设总边数为`S`，节点总数为`n`，叶子节点数为`n0`,度为1的结点数为`n1`,度为2的结点数为`n2`

1.  总结点：`n = n0 + n1 + n2`
2.  总边数：`S = n - 1` （除根节点外，其他节点都有其父结点所指向）
3.  总边数：`S = n2 * 2 + n1 * 1 + n0 * 0` (度为2说明指向两条边，度为1指向1条边，叶子节点不指向。)

2 3 => 4. `n = n2 * 2 + n1 + 1`

1 4 => `n0 = n2 + 1`

1.  #### 完全二叉树或者是满二叉树，按照从上到下，从左往右进行编号，那么设某一结点下标为i，如果 i = 1，则结点i是二叉树的根，无双亲，如果i > 1,则`双亲是结点[i/2]`（向下取整），如果2i > n,则 i 为叶子节点，无左孩子，否则`左孩子是结点2i`，如果2i + 1 > n，则结点i无右孩子，否则，其`右孩子是结点2i + 1` ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center 1]

1.  #### 具有n个结点的完全二叉树的深度为k ####
    
     k = ⌊ l o g 2 n ⌋ + 1 k = \\lfloor log\_2n\\rfloor+1 k=⌊log2n⌋\+1

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center 2]

> 对于完全二叉树而言，每行第一个结点下标为`2^（当前层数 - 1）`,所以完全二叉树结点最少时，深度为logn + 1，满二叉树时最后一个结点下标为`2^(当前层数) - 1`，当完全二叉树达到 满二叉树时，深度为log(n+1),对于该层而言，无论是满二叉树还是最底层只有一个结点的完全二叉树，他的结点下标处在`[ 2^上层层数，2^当前层数 )`,所有`logn向下取整并加上1`，得到的总是当前的深度。

1.  #### `n`个节点的二叉树有`f(n)`种形态(`Catalan数`,太难不会证明qaq) ####

f ( n ) = ( 2 n ) ! n ! ( n + 1 ) ! f(n) = \{(2n)!\\over n!(n+1)!\} f(n)=n!(n\+1)!(2n)!

或者是  
 f ( n ) = C 2 n n − C 2 n n − 1 f(n) = C\_\{2n\}^n - C\_\{2n\}^\{n-1\} f(n)=C2nn−C2nn−1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200703231750257.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200703231806207.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200703231835609.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1,size_16,color_FFFFFF,t_70#pic_center