05-5.1.1~2 树的定义和基本术语

本文主要是介绍05-5.1.1~2 树的定义和基本术语，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 👋 Hi, I’m @Beast Cheng
• 👀 I’m interested in photography, hiking, landscape…
• 🌱 I’m currently learning python, javascript, kotlin…
• 📫 How to reach me --> 458290771@qq.com

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

基本概念

最初始的结点是根结点
结点和结点连接起来的线叫做边
下面还有结点的的结点叫做分支结点
下面没有结点的结点叫做叶子结点
结点数为0的树叫做空树 $\varphi$
与之对应的树叫做非空树

• 有且只有一个根节点
• 只有根结点没有前驱，其他的结点都能找到对应的前驱
• 只有叶子结点没有后继，其他的结点都能找到对应的后继
• 除了根结点外，任何一个结点都有且仅有一个前驱
• 每个结点可以有0个或多个后继
  当$n>1$时，其余结点可分为$m(m>0)$个互不相交的有限集合$T_1,T_2,...,T_m$，其中每个集合本身又是一棵树，并且称为根结点的子树

基本术语

结点之间关系的描述

什么是祖先结点？

从当前结点往根结点出发，直到根结点为止，中间经过的所有结点，都是祖先结点

什么是子孙结点？

从当前结点出发，往下的分支都是它的子孙结点

什么是双亲结点（父结点）？

一个结点的直接前驱就是父结点

什么是孩子结点？

一个结点的直接后继

什么是兄弟结点？

一个结点的多个直接结点就是兄弟结点

什么是堂兄弟结点？

与当前结点同一级的，并且不是同一个父结点的结点，叫做堂兄弟结点

什么是两个结点之间的路径？

也就是两个结点之间的线，需要注意的是，这个路径只能是从上到下的

什么是路径长度？

经过几条边，长度就是多少

结点、树的属性描述

结点的层次（深度）——从上往下数（默认从0开始，但是要注意审题）
结点的高度——从下往上数
树的高度（深度）——总共有多少层
结点的度——有几个分支
树的度——各结点的度的最大值

有序树、无序树

有序树——逻辑上看，树中各结点的各子树从左至右是有次序的，不能互换
无序树——逻辑上看，树中各结点的各子树从左至右是无次序的，可以互换
具体看你用树存什么，是否需要用结点的左右位置反映某些逻辑关系，如果需要就用有序树

森林

森林——$m(m>0)$棵互不相交的树的集合
m可以为0，也就是空森林

这篇关于05-5.1.1~2 树的定义和基本术语的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---