树的定义与表示
知识总结
树的基本概念
- 树：n个节点的有限集合，n=0时为空树
- 根节点：没有父节点的节点
- 叶节点（叶子）：没有子节点的节点
- 内部节点：既有父节点又有子节点
- 深度：从根到该节点的路径长度（根的深度为0或1，注意题目定义）
- 高度：从该节点到最深叶节点的路径长度
- 度：节点的子节点个数
树的重要性质
- n个节点的树有 n-1 条边
- 树中任意两个节点之间有且仅有一条路径
- 度为m的树，第i层最多有 m^(i-1) 个节点（根为第1层）
树的存储方式
- 父亲表示法：每个节点记录父节点编号
- 孩子表示法：每个节点存储子节点列表
- 孩子兄弟表示法：左孩子右兄弟（将多叉树转为二叉树）
森林
多棵互不相交的树的集合称为森林。
- 森林可以转换为二叉树（左孩子右兄弟法）
- 二叉树也可以还原为森林