文章目录
1. 树
1.1. 树的基本概念和基本术语
1.1.1 树的基本概念
1. 树有两种情况
1. 空树：结点树为0的树.
* 注意：空树也是树。
2. 非空树
* 特点
1. 一棵树有且只有一个根结点。
2. 除了根结点以外，每个结点有有且只有一个前驱。
3. 每个结点可以有0个或多个后继。
4. 没有后继的结点称为“叶子结点”（或终端结点）
5. 有后继的结点称为“分支结点”（或非终端结点）。根结点也是分支结点。
2. 子树：每个结点的子孙结点可以分为互不相交的有限集合，而每一个集合又是一棵树，并且称为该结点的子树。
* 注意：从子树的概念，我们可以看出树是递归定义的。
子树的例子：
1.1.2 基本术语
1.1.2.1 结点之间的关系
1. 双亲结点(父结点)：该结点的前驱结点称为该结点的父节点。
2. 孩子结点：该结点的后继结点称为该结点的孩子结点。
3. 祖先结点：该结点的父结点，父结点的父结点，父结点的父结点的父结点...一直到根结点都是该结点的祖先结点。
* 注意：祖先结点包括父结点
4. 子孙结点：该结点的孩子结点，孩子结点的孩子结点，孩子结点的孩子结点的孩子结点...一直到叶子结点都是该结点的子孙结点。
* 注意：子孙结点包括孩子结点
5. 兄弟结点：有相同前驱的结点，称为兄弟结点。
6. 堂兄弟结点：两个结点的父节点有相同的前驱，称为堂兄弟结点。
7. 两个结点间的路径：只能从上到下，因为树的边是又向的，指向叶子结点。
8. 路径长度：两个结点间的路径经过几条边。
1.1.2.2 结点、树的属性
1. 结点的层次(深度)：从上往下数。
2. 结点的高度：从下往上数。
3. 数的高度(深度): 总共有多少层。
4. 结点的度：有几个孩子。(指出结点的边数)
5. 树的度：各结点的度的最大值。
* 注意：以上从上往下或者从下往上数时，默认从1开始数。如果题目给出从0开始数，就从0开始数。
1.1.2.3 有序树和无序树
1. 有序树：逻辑上看，树中结点的各子树从左到右是有次序的，不能交换。
2. 无序树：逻辑上看，树中结点的各子树从左到右是无次序的，可以交换。
* 注意：要用有序树还是无序树，主要看是否需要用结点的左右位置反映某些逻辑关系。
1.1.2.4 森林
1. 森林：是m(m>=0)颗互不相交的树的集合。
* 注意：m=0，为空森林。
1.1.3 小结
注意：树的度与图的度不一样。树的某个结点的度指的是该结点的出度，而图的某个结点的度是入度与出度之和。
1.2 树的重要知识点
1.2.1 六个考点
小结：总结起来就是
- 树的结点总数与结点度的关系。
- 树的结点总数与树的高度的关系。
1.2.2 小结
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/84609.html
