- 👋 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+n2
- n = 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
