1、树的存储结构
》》 树的存储方式有多种，既可以采用“ 顺序存储结构 ”，也可以采用“ 链式存储结构 ”，但是无论采用何种
存储方式，都要求唯一地反映树中各结点之间的逻辑关系，这里介绍 3 种常用的存储结构：
双亲表示法 、 孩子表示法 、 孩子兄弟表示法
》》 双亲表示法
这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个“ 伪指针 ” ，指示其
双亲结点在数组中的位置。如下图所示：
补充：双亲表示法的存储结构利用了每个节点（除了根结点外）只有唯一双亲的性质，可以很快
得到每个结点的双亲结点，但是求孩子时却需要遍历整个结构。
》》 孩子表示法
孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，则 N 个结点就有
N 个孩子链表（叶子结点的孩子链表为空表）。如下图所示：
补充1： 孩子表示法，存储每个结点的值，以及所有孩子的链接。
补充2： 按树的度（即树中结点度的最大值）设计结点的孩子结点指针域个数。
》》 孩子兄弟表示法
*** 孩子兄弟表示法又称为“ 二叉树表示法 ” ，即以二叉链表作为树的存储结构。孩子兄弟表示法
是使每个结点包括三部分内容：结点值、指向结点第一个孩子节点的指针、指向结点下一个兄
弟结点的指针（沿此域可以找到结点的所有兄弟结点），如下图所示：
2、树、森林与二叉树的转换
》》 1）、由于二叉树和树都可以用 “ 二叉树链表 ” 作为存储结构，则以二叉树链表作为媒介
可以导出树与二叉树的一个对应关系，即给定一棵树，可以找到唯一的一棵二叉树与
之对应。
从物理结构上来看，树的孩子兄弟表示法与二叉树的二叉树链表表示法相同，即每个
节点共有两个指针，分别指向“ 结点第一个孩子结点” 和 “ 结点的下一个兄弟结点 ”，而
二叉树链表使用双指针。因此，就可以用同一存储结构的不同解释将一棵树转换为二叉树。
2）、树转换为二叉树的规则：每个结点左指针指向它的第一个孩子结点，右指针指向它在树中
相邻兄弟结点，可表示为“ 左孩子右兄弟 ”。由于根结点没有兄弟，所以，由树转换而得的
二叉树没有右子树。
3）、将森林转换为二叉树的规则：
a. 先将森林中的每一棵转换为二叉树，再将第一棵树的根作为转换后的二叉树的根。
b. 第一棵树的左子树作为转换后二叉树根的左子树。
c. 第二棵树作为转换后二叉树的右子树，第三棵树作为转换后二叉树根的右子树的右子树，
以此类推，就可以将森林转换为二叉树。
4）、二叉树转换为森林的规则：
若二叉树非空，则二叉树根及其左子树为第一棵树的二叉树形式，二叉树根的右子树又
可以看做是一个由除第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后产生
一棵没有右子树的二叉树为止，这样就得到了原森林。（二叉树转换为树或森林是唯一的）
3、树和森林的遍历
》》树的遍历方式
树的遍历是以某种方式访问树中的每一个结点，且仅访问一次。树的遍历操作主要有
“ 先根遍历 ” 和 “ 后根遍历 ” 。
1）、先根遍历：若树非空，则先访问根结点，再按从左到右的顺序遍历根结点的每一棵子树。
其访问顺序与这棵树相应二叉树的先序遍历顺序相同。
2）、后根遍历：若树非空，则按从左到右的顺序遍历根结点的每一棵树，之后再访问根结点。
其访问顺序与这棵树相应二叉树的中序遍历顺序相同。
3）、树也有层次遍历，与二叉树的层次遍历思想基本相同，即按层序依次访问各结点。
》》 森林的遍历方式
森林的遍历方式有两种，“ 先序遍历森林” 和 “ 中序遍历森林”。
1）、先序遍历森林。若森林非空，则按如下规则进行遍历：
## 访问森林中第一棵树的根结点
## 先序遍历第一棵树中根结点的子树森林
## 先序遍历除去第一棵树之后剩余的树构成的森林
2）、中序遍历森林。若森林非空，则按如下规则进行遍历：
## 中序遍历森林中的第一棵树的根结点的子树森林
## 访问第一棵树的根结点
## 中序遍历除去第一棵树之后剩余的树构成的森林
》》 树和森林的遍历：可采用对应二叉树的遍历算法来实现
4、树的应用 ---- 并查集
》》 并查集是一种简单的集合表示，它支持以下 3 种操作：
1）、Union( S , Root1 , Root2 ) ：把集合 S 中的子集合 Root2 并入子集合 Root1 。要求
Root1 和 Root2 互不相交，否则不执行合并。
2）、 Find( S , x ) : 查找集合 S 中单元素 x 所在的子集合，并返回该子集合的名字。
3）、 Initial( S ) : 将集合 S 中每一个元素都初始化为只有一个单元素的子集合。
转载：https://blog.csdn.net/lierming__/article/details/102156888