5.1.3 树的性质

教材导航 · 第5章

原书定位

印刷页P126起,对应PDF第138页。下文为目视整理的知识提要;完整内容见原书对照。

设度为 ii 的结点有 nin_i 个,总结点数为 nn:

n=∑ini,n−1=∑iini,n0=1+∑i≥2(i−1)nin=\sum_i n_i,\qquad n-1=\sum_i i n_i,\qquad n_0=1+\sum_{i\ge2}(i-1)n_i

最大分支数为 m>1m>1 时,第 ii 层最多 mi−1m^{i-1} 个结点,高 hh 时最多 (mh−1)/(m−1)(m^h-1)/(m-1) 个结点,最小可能高度为 ⌈log⁡m(n(m−1)+1)⌉\lceil\log_m(n(m-1)+1)\rceil。

若树的度恰为 mm,至少有一个结点有 mm 个孩子,因此最大高度为 n−m+1n-m+1;若只规定度不超过 mm,则可为单链,高度达到 nn。有 tt 棵树、nn 个结点的森林共有 n−tn-t 条边。

对应练习

5.1 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P126,PDF第138页