在线学习
重点科目
初中数学
高中数学
高等数学
线性代数
概率统计
高中物理
数学公式
主要科目
复变函数
离散数学
数学分析
实变函数
群论
数论
未整理科目
近世代数
数值分析
常微分方程
偏微分方程
大学物理
射影几何
微分几何
泛函分析
拓扑学
数学物理
趣味数学
科数网
题库
教材
高考区
考研区
VIP
科数网
题库
在线学习
高中数学
高等数学
线性代数
概率统计
高中物理
复变函数
离散数学
你好
游客，
登录
注册
在线学习
离散数学
旧数据
树
树的顶点与遍历
最后
更新:
2025-01-21 16:09
查看:
33
次
反馈
刷题
树的顶点与遍历
## 完全m元树的顶点数 设 T 是完全 m 元树， 若T有 n 个顶点，则有 $i =( n -1) / m$ 个内点和 $l=[( m -1) n +1] / m$ 个树叶． 若 $T$ 有 $i$ 个内点，则有 $n = mi +1$ 顶点和 $l=( m -1) i +1$ 个树叶． 若 T 有 $l$ 个树叶，则有 $n =( m l-1) /( m -1)$ 个顶点和 $i =(l-1)) /( m -1)$ 个内点． $n - 1 = m \times i \quad$（入度总数 $=$ 出度总数） $n = i + l$（顶点分为内点和树叶） ## 高度为 $h$ 的 $m$ 元树的顶点数 －高度为 $h$ 的 $m$ 元树最多有个 $m^h$ 个树叶。 －按照高度 $h$ 进行归纳证明。（第 1 层顶点最多为 $m$ 个） －若高度为 h 的 m 元树有 $l$ 个树叶，则 $h \geq\left\lceil\log _{ m } l\right\rceil$ ． －如果这棵树是完全的且平衡的，则有 $h =\left\lceil\log _{ m }\right\rceil$ ． $$ m ^{h-1}<l \leq m ^{h} $$ ## 有序根树的遍历 ### 前序遍历（preorder） －T只包含根 $r$ ，则为 $r$ ； －$T$ 的子树为 $T_1, \ldots, T_n$ ，则为 $r$ ， $\operatorname{preorder}\left(T_1\right), \ldots$ ， $\operatorname{preorder}\left(T_n\right)$   ### 后序遍历 （postorder）  ## 中序遍历 （inorder）//先访问第一棵子树 
刷题
做题，是检验是否掌握数学的唯一真理
上一篇：
根树的定义
下一篇：
表达式的根树表示
本文对您是否有用？
有用
(
0
)
无用
(
0
)
纠错
高考
考研
关于
赞助
公式
科数网是专业专业的数学网站。