树的基本概念

笔记内容来源于B站数据结构课程

定义

树是 n(n>=0) 个结点的有限集合，n=0 时，称为空树，这是一种特殊情况。在任意一颗非空树中应满足：

1. 有且仅有一个特定的称为根的结点
2. 当 n>1 时，其余结点可分为 m(m>0) 个互不相交的有限集合T1,T2,...,Tm，其中每个集合本身又是一颗树，并且称为根节点的子树
3. 每个非根结点有且仅有一个前驱结点

结点关系

祖先结点：从一个结点出发，沿边向上直到根结点的结点都是其祖先结点。
子孙结点，从一个结点出发，沿边向下直到叶子结点的结点都是其子孙结点。
双亲结点：从一个结点出发，沿边向上的直接结点是其双亲结点。
孩子结点，从一个结点出发，沿边向下的直接结点是其孩子结点。
兄弟结点：同双亲的结点。
堂兄弟结点：同层但不同双亲的结点。
路径：两个结点的路径只能从上到下。
路径长度：两个结点路径经过边的数目。

属性

结点的层次（深度）：从上往下数
结点的高度：从下往上数
树的高度（深度）：总共多少层
结点的度：有几个孩子（分支）
树的度：各结点的度的最大值

有序树和无序树

有序树：树中结点的各子树从左至右是有次序的，不能互换。
无序树：树中结点的各子树从左至右是无次序的，可以互换。

树和森林

森林：m(m>=0) 棵互不相交的树的集合。