AdaCpp

C++ IDE C++ 学习基础练习代码评测特惠套餐

树的定义与表示 - CSP-J初赛冲刺课 | AdaCpp

CSP-J初赛冲刺课

1. 课程介绍免费 2. 计算机发展史 3. 计算机组成 4. 计算机网络 5. 计算机语言 6. 计算机内置函数 7. 基础算法概念 8. 链表 9. 栈 10. 队列 11. 树的定义与表示 12. 二叉树的遍历 13. 特殊二叉树 14. 图的存储与定义 15. 图的连通性 16. 拓扑排序 17. 素数问题汇总 18. 欧几里得算法 19. 进制转换 20. 计算机编码 21. 哈夫曼编码 22. 格雷码

树的定义与表示

课程文档

知识总结

树的基本概念

树：n个节点的有限集合，n=0时为空树
根节点：没有父节点的节点
叶节点（叶子）：没有子节点的节点
内部节点：既有父节点又有子节点
深度：从根到该节点的路径长度（根的深度为0或1，注意题目定义）
高度：从该节点到最深叶节点的路径长度
度：节点的子节点个数

树的重要性质

n个节点的树有 n-1 条边
树中任意两个节点之间有且仅有一条路径
度为m的树，第i层最多有 m^(i-1) 个节点（根为第1层）

树的存储方式

父亲表示法：每个节点记录父节点编号
孩子表示法：每个节点存储子节点列表
孩子兄弟表示法：左孩子右兄弟（将多叉树转为二叉树）

森林

多棵互不相交的树的集合称为森林。

森林可以转换为二叉树（左孩子右兄弟法）
二叉树也可以还原为森林