数据结构笔记——二叉树的常考性质

你的名字 2023-02-11 07:21 2阅读 0赞

**目录**

一、二叉树的常考性质

考点1

考点2

考点3

二、完全二叉树的常考性质

考点1

考点2

三、总结

## **一、二叉树的常考性质** ##

### **考点1** ###

设非空二叉树中度为0、1和2的结点个数分别为n0,n1和n2，则**n0 = n2 + 1**（叶子结点比二分支结点多一个）

假设树中结点总数为n，则

①n = n0 + n1 + n2

②n = n1 + 2n2 + 1（树的结点数 = 总度数 + 1）

![20200522113502174.png][]

### **考点2** ###

二叉树第i层至多有2^(i-1)个结点

m叉树第i层至多有m^(i-1)个结点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]

### **考点3** ###

高度为h的二叉树至多有2^h - 1个结点（满二叉树）

高度为h的m叉树至多有m^h - 1/m -1 个结点

![20200522113843688.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1][]

## **二、完全二叉树的常考性质** ##

### **考点1** ###

![20200522114240704.png][]

![20200522114328780.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2][]

![20200522114509844.png][]

![20200522114530190.png][]

![2020052211455646.png][]

### **考点2** ###

对于完全二叉树，可以由结点数n推出度为0、1和2的结点个数为n0,n1,n2

![20200522114735167.png][]

![202005221148041.png][]

## **三、总结** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3][]

[20200522113502174.png]: https://img-blog.csdnimg.cn/20200522113502174.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200522113745687.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200522113843688.png]: https://img-blog.csdnimg.cn/20200522113843688.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200522113852923.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200522114240704.png]: https://img-blog.csdnimg.cn/20200522114240704.png
[20200522114328780.png]: https://img-blog.csdnimg.cn/20200522114328780.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200522114411666.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200522114509844.png]: https://img-blog.csdnimg.cn/20200522114509844.png
[20200522114530190.png]: https://img-blog.csdnimg.cn/20200522114530190.png
[2020052211455646.png]: https://img-blog.csdnimg.cn/2020052211455646.png
[20200522114735167.png]: https://img-blog.csdnimg.cn/20200522114735167.png
[202005221148041.png]: https://img-blog.csdnimg.cn/202005221148041.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200522114814573.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70