【数据结构】二叉树的性质随想总结

水深无声 2021-09-21 08:16 281阅读 0赞

二叉树的性质

1.  在二叉树的第i层最多有 2 i − 1 2^\{i-1\} 2i−1个节点( i ≥ 1 i\\geq1 i≥1)，其中i为层数
2.  深度为k的二叉树最多多有 2 k − 1 2^k-1 2k−1个节点( k ≥ 1 k\\geq1 k≥1)，其中k为树的深度
3.  对于任意一棵二叉树，如果其叶节点为 n 0 n\_0 n0, 度为二的节点 n 2 n\_2 n2, 则有 n 0 = n 2 + 1 n\_0 = n\_2 +1 n0=n2\+1

如果树为满二叉树(节点只能在最大的两层出现)

1.  具有n个节点的完全二叉出的深度为 ⌊ log ⁡ 2 n ⌋ + 1 \\lfloor\\log\_2n\\rfloor+1 ⌊log2n⌋\+1
2.  如果对一棵有n个节点的完全二叉树的节点按层序编号, 则对任意节点i有:
    
     *  如果i=1则节点i是二叉树的根, 无双亲; 如果i>1则其双亲节点是 ⌊ i / 2 ⌋ \\lfloor i /2 \\rfloor ⌊i/2⌋
     *  如果2i>n, 则i节点无左孩子(i为叶子节点); 否则其左孩子是节点 2 i 2i 2i
     *  如果2i+1>n, 则i无右孩子; 否则其右孩子 2 i + 1 2i+1 2i\+1

--------------------

想透彻理解知识需要不断问为什么, 这样才可以深刻记忆和理解知识. 下面是一点随想.

**为什么二叉树第i层最多有 2 i − 1 2^\{i-1\} 2i−1个节点??**  
二叉树, 它最基本的定义是, 一棵最多有两个子节点(孩子)的树, 且它的左右孩子是有序的.  
如果是一块满二叉树, 那么, 第一层有1节点, 第二层有2个节点, 第三层有4个节点…可以推出第四层有8个节点…  
即1 2 4 8…  
根据二叉树的性质又可以表示为: 2 0 2 1 2 2 2 3 . . . . 2^0 \\quad 2^1 \\quad 2^2 \\quad 2^3 .... 20212223.... 它是一个等比数列, 它的q=2, 这是一个很有意义的等比数列.  
满二叉树的每一次就代表了二叉树每一层节点的最大值, 因此二叉树每一层最大值是 2 i − 1 2^\{i-1\} 2i−1, i是层数.

**为什么深度为k的二叉树最多多有 2 k − 1 2^k-1 2k−1个节点???**  
算满二叉树的k层就代表了, 二叉树k层最多的节点数.  
求k层最大的节点的公式, 直接用等比数列前n项和公式推出来emm.

**插张等比数列基本公式:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70]  
求满二叉树前n层节点的和, 已知 a 1 = 1 和 q = 2 a\_1=1和q=2 a1=1和q=2, 带入 s n = a 1 ∗ ( 1 − q n ) / ( 1 − q ) s\_n = a\_1\*(1-q^n)/(1-q) sn=a1∗(1−qn)/(1−q)得 ( 1 − 2 n ) / ( − 1 ) (1-2^n)/(-1) (1−2n)/(−1)  
最终推得:  2 n − 1 2^n-1 2n−1

ps:这里的是笔者随想而写的, 并不具有数学推理的严谨性.

--------------------

> **想了解作者更多，请移步我的个人网站，欢迎交流、留言~**  
> **极客技术空间：[https://elltor.com/][https_elltor.com]**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70]: /images/20210920/0eba75761d414849bd8ed1228639c5f2.png
[https_elltor.com]: https://elltor.com/