- 👋 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：结点数 = 总度数 + 1
常见考点2：度为m的树、m叉树的区别
树的度——各结点的度的最大值
m叉树——每个结点最多只能有m个孩子的树
| 度为m的树 | m叉树 |
|---|---|
| 任意结点的度 ≤ m \leq m ≤m（最多m个孩子） | 任意结点的度 ≤ m \leq m ≤m（最多m个孩子） |
| 至少有一个结点度 = m（有m个孩子） | 允许所有结点的度都 < m < m <m |
| 一定是非空树，至少有 m + 1 m+1 m+1个结点 | 可以是空树 |
常见考点3：度为 m 的树第 i 层至多有 m i − 1 m^{i-1} mi−1个结点（ i ≥ 1 i \geq 1 i≥1 ）
常见考点4：高度为 h 的 m 叉树至多有 m h − 1 m − 1 \frac{m^h-1}{m-1} m−1mh−1个结点
等比数列求和公式：
a + a q + a q 2 + . . . + a q n − 1 = a ( 1 − q n ) 1 − q a+aq+aq^2+...+aq^{n-1}=\frac{a(1-q^n)}{1-q} a+aq+aq2+...+aqn−1=1−qa(1−qn)
常见考点5：高度为 h 的 m 叉树至少有 h 个结点；高度为 h、度为 m 的树至少有 h+m-1 个结点
常见考点6：具有 n 个结点的 m 叉树的最小高度为： l o g m ( n ( m − 1 ) + 1 ) log_{m}(n(m-1)+1) logm(n(m−1)+1)
高度最小的情况：所有结点都有 m 个孩子
m h − 1 < n ( m − 1 ) + 1 ≤ m h m^{h-1}<n(m-1)+1\leq m^h mh−1<n(m−1)+1≤mh
从而
h − 1 < l o g m ( n ( n − m ) + 1 ) ≤ h h-1<log_{m}(n(n-m)+1)\leq h h−1<logm(n(n−m)+1)≤h
所以
h m i n = l o g m ( n ( m − 1 ) + 1 ) h_{min}=log_m(n(m-1)+1) hmin=logm(n(m−1)+1)