基础概念
相关提炼内容见 tree。
树的定义
- 树的特点
- 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱
- 树中所有结点可以有零个或多个后继
基本术语
- 根结点：非空树种无前驱结点的结点
- 结点的度：结点拥有的子树数
- 树的度：树内各结点的度的最大值
- 叶子（终端结点）：没有后继元素（度 = 0）
- 分支结点（非终端结点）：度 != 0；
- 内部结点：根结点以外的分支结点
- 孩子，双亲：结点的子树的根称为该结点的孩子，该结点称为孩子的双亲
- 兄弟结点：有共同的双亲
- 堂兄弟：双亲在同一层的结点
- 结点的祖先：从根到该结点所经分支上的所有结点
- 结点的子孙：以某结点为根的子树中的任一结点
- 树的深度：树中结点的最大层次
- 有序树：树中结点的各子树从左至右有次序（最左边为第一个孩子）
- 无须树：树中结点的各子树无次序
- 森林：是 m（m≥0）棵互不相交的树的集合，把根结点删除，树就变成了森林，一棵树可以看成是一个特殊的森林，给森林中的各子树加上一个双亲结点，森林就变成了树（树一定是森林，森林不一定是树）
树的性质
- 树中的结点数等于―所有结点的度数之和+1
- 度为 m 的树中第 i 层上至多有个结点（i≥1）
- 高度为 h 的 m 叉树至多有 个结点
- 具有 n 个结点的 m 叉树的最小高度为
习题
- 思考：树中的结点数等于 → 所有结点的度数之和+1
- 3 树的路径长度是从树根到每个结点的路径长度的什么 → 总和，注意与哈夫曼树的带权路径长度的区别
- 7 【2010】在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶节点个数为多少 ?→82