逻辑结构
n个结点的有限集。
在任意一棵树应满足：
- 有且仅有一个结点称为根结点
- n>1时，其余结点可分为m个互不相交的有限集，其中每个集合又是一棵树
树的定义是递归的。
特点
- 树的根结点没有前驱，除此之外，所有结点有且只有一个前驱。
- 树中所有结点可以有0个或多个后继。
概念
- 根A到结点K的唯一路径上的任意结点，称为结点K的祖先。结点K是这些结点的子孙。最接近结点K的结点称为双亲，结点K是它的孩子。
- 树中一个结点的孩子个数称为该结点的度。树中结点的最大度数称为树的度。
- 度>0的结点称为分支节点（非终端结点），度=0的结点称为叶子结点（终端结点）。
- 根结点为第一层，子节点为第二层......在同一层的结点互为堂兄弟。
- 结点的深度是从根结点自顶向下逐层累加的。
- 结点的高度是从叶节点自底向上逐层累加的。
- 树的高度（或深度）是树中结点的最大层数。
- 树中各结点的子树从左到右都是有次序的，不能互换，称为有序树。
- 路径是两个结点之间的结点序列，路径长度是路径上所经过的边的个数。
由于树中的分支是有向的（从双亲指向孩子），所以树中的路径是从上到下的。
堂兄弟之间不存在路径
- 互不相交的树的集合，称为森林。
只要把树的根节点去掉，就成了森林。
反之，森林中的多个树加上根结点，他们就成了同一颗树。
性质
- 树中的结点数 = 所有结点的度数和+1（根结点）
- 度为m的树中第i层上至多有mi-1个结点
- 高度为h的m叉树至多有(mh-1)/(m-1)个结点
- 具有n个结点的m叉树的最小高度为logm(n(m-1)+1)
第一条性质换言之，在n个结点的树中有n–1条边。如若森林有15条边，25个结点，则该森林包含树的个数为10（25-15=10）
物理结构
双亲表示法
用一组连续的地址空间，存储每个结点，结点中增设一个伪指针，指示其双亲结点在数组中的位置。
- 得到双亲结点：O(1)
- 得到子结点：O(n)
孩子表示法
将每个结点的孩子结点都用单链表链接起来形成一个线性结构。
- 得到子节点：O(1)
- 得到双亲结点：O(n)
孩子兄弟表示法
又称为二叉树表示法。
每个结点包括：数据域、指向结点第一个孩子的指针、指向结点下一个兄弟的指针。
可以方便地实现树转化为二叉树的操作。
- 得到子节点：O(1)
- 得到双亲结点：O(n)
树的基本操作
树转化为二叉树：
- 在兄弟结点之间添加一条线
- 对于每个结点，只保留它与第一个孩子的连线，与其他孩子的连线全部抹掉
- 以树根为轴心，顺时针旋转45°
先根遍历
若树非空，先访问根结点，再依次访问根结点的每棵子树，遍历子树时仍遵循先根后子树的原则。（与二叉树的先序遍历相同）
后根遍历
若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵循先子树后根的原则。（与二叉树的中序遍历相同，因为树转化为二叉树后根结点是没有右子树的）
森林的基本操作
森林转化为二叉树：
- 将森林中的每棵树转化为二叉树
- 每棵树的根视为兄弟关系，在各树的根之前加一条连线
- 以第一棵树的根为轴心顺时针旋转45°
二叉树转化为森林：
- 将根的右链断开，根的右子树又可视为除第一棵树外的森林转换后的二叉树
- 重复1.直至只剩一棵没有右子树的二叉树为止
- 将每棵二叉树依次转换成树，就得到了原森林
二叉树转为树或森林是唯一的
先序遍历森林
若森林非空，先访问森林中第一棵树的根结点，然后先序遍历第一棵树根结点的子树森林，之后先序遍历除第一棵树外剩余的树构成的森林。
中序遍历森林（后根遍历森林）
若森林非空，先中序遍历森林中第一棵树的根结点的子树森林，然后访问第一棵树的根结点，之后中序遍历除第一棵树外剩余的树构成的森林。
当森林转换为二叉树时，第一棵树的子树森林转化为左子树，剩余树的森林转化为右子树。
所以森林的先序遍历与中序遍历对应二叉树的先序遍历和中序遍历。
树与森林的遍历与二叉树遍历的对应关系：
| 树 | 森林 | 二叉树 |
|---|---|---|
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |
应用
并查集
通常用树（或森林）的双亲表示作为并查集的存储结构。
每个子集用一棵树表示，所有表示子集和的树，构成表示全集合的森林，存放在双亲表示数组内。
并运算（U）时，将其中一个子集和的根结点的双亲结点指向另一个集合的根结点。
判断两个元素是否属于同一集合，只需要分别找到它们的根结点，比较根结点是否相同即可。