05-5.2.1_2 二叉树的性质
- 👋 Hi, I’m @Beast Cheng
- 👀 I’m interested in photography, hiking, landscape…
- 🌱 I’m currently learning python, javascript, kotlin…
- 📫 How to reach me –> 458290771@qq.com
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑💻
此外，《程序员必备技能》专栏日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏
常见考点1
设非空二叉树中度为 0、1 和 2的结点个数分别为
n
0
,
n
1
和
n
2
n_0, n_1 和 n_2
n0,n1和n2，则
n
0
=
n
2
+
1
n_0=n_2+1
n0=n2+1（叶子节点比二分支结点多一个）
假设树中结点总数为 n ，则
n
=
n
0
+
n
1
+
n
2
n=n_0+n_1+n_2
n=n0+n1+n2n
=
n
1
+
2
n
2
+
1
n=n_1+2n_2+1
n=n1+2n2+1 （树的总结点数 = 总度数 + 1）
常见考点2
二叉树第
i
i
i 层至少有
2
i
−
1
2^{i-1}
2i−1 个结点（
i
≥
1
i \geq 1
i≥1）
m
m
m 叉树第
i
i
i 层至多有
m
i
−
1
m^{i-1}
mi−1 个结点（
i
≥
1
i \geq 1
i≥1）
常见考点3
高度为
h
h
h 的二叉树至多有
2
h
−
1
2^h-1
2h−1 个结点（满二叉树）
高度为
h
h
h 的
m
m
m 叉树至多有
m
h
−
1
m
−
1
\frac{m^h-1}{m-1}
m−1mh−1 个结点
完全二叉树的常考性质
常见考点1
具有
n
n
n 个
（
n
>
0
）
（n>0）
（n>0）结点的 完全二叉树的高度
h
h
h 为
l
o
g
2
(
n
+
1
)
log_2(n+1)
log2(n+1) 或
l
o
g
2
n
+
1
log_2n+1
log2n+1
高度为 h 的满二叉树共有
2
h
−
1
2^h-1
2h−1 个结点
高为 h-1 的满二叉树共有
2
h
−
1
−
1
2^{h-1}-1
2h−1−1 个结点
高为 h 的完全二叉树至少有
2
h
−
1
2^{h-1}
2h−1 个结点，至多有
2
h
−
1
2^h-1
2h−1 个结点
如果一个结点的编号为 i ，那么它所在的层次也满足以上式子：
l
o
g
2
(
n
+
1
)
log_2(n+1)
log2(n+1) ，
l
o
g
2
n
+
1
log_2n+1
log2n+1
常见考点2
对于完全二叉树，可以由结点总数 n 推出度为 0，1，2的结点个数为
n
0
,
n
1
,
n
2
n_0,n_1,n_2
n0,n1,n2
这个基于我们之前的结论：
- 完全二叉树最多只有一个度为 1 的结点，也就是说
n
1
=
0
,
1
n_1=0,1
n1=0,1 - 由
n
0
=
n
2
+
1
n_0=n_2+1
n0=n2+1 –>n
0
+
n
2
n_0+n_2
n0+n2 一定是奇数
因此 - 如果完全二叉树有 2k 个（偶数）结点，则必有：
n
1
=
1
,
n
0
=
k
,
n
2
=
k
−
1
n_1=1,n_0=k,n_2=k-1
n1=1,n0=k,n2=k−1 - 如果完全二叉树有 2k-1 个（奇数）结点，则必有：
n
1
=
0
,
n
0
=
k
,
n
2
=
k
−
1
n_1=0,n_0=k,n_2=k-1
n1=0,n0=k,n2=k−1
