树与森林

一、
树的存储结构有很多种形式，今天就谈谈树的三种常用的链表存储方式吧。
双亲表示法：由于树中的每个结点都有唯一的一个双亲结点，所以用一组连续的存储空间（一维数组）存储树中的各个结点，一个数组元素表示树的一个结点，每个结点含两个域，数据域存放结点本身信息，双亲域指示本结点的双亲结点在数组中位置。

孩子表示法：树中的每个结点可能有多棵子树，则可用多重链表表示，即每个结点有多个指针域，其中每个指针域指向一棵子树的根结点。这样的话，会存在两种结点格式。

微信图片_20180306161926.png

第一种结点格式结点是同构的，d为树的度（分支数目）。因为大多数的结点的度都小于d，则会有很多空链域。n个结点度为k的树中必有n(k-1)+1个空链域。

第二种结点格式不是同构的，d为结点度，degree域的值同d，节约空间，但操作不方便。

两种格式的区别在于：第一种格式是默认以树的度为为d的值。 而第二种格式是以结点的度为d的值，也就是degree的值。

另一种孩子表示法：每个结点的孩子结点排列起来，成一个线性表，以单链表作存储结构。n个结点有n个孩子链表（叶子的孩子链表为空表）。最后n个头指针又组成一个线性表。
孩子表示法与孩子双亲表示法，如下图：

微信图片_201803061716212.png

孩子兄弟表示法（二叉树表示法）：在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域fch和nsib，即可得树的孩子兄弟链表表示。
如图：

微信图片_201803061716211.png

二、森林与二叉树的转换
森林(Forest)：m(m≥0)棵树的集合。

因为二叉树和树都可用二叉链表作为存储结构，那么树就可以转换为一棵唯一的二叉树，二叉树也可转换为树。

如图： 微信图片_20180306170850.png

那么同理，把森林中第二棵树的根节点看成是第一棵树的根节点的兄弟。则同样可导出森林和二叉树的对应关系。

如图： 微信图片_20180306171051.png

所以可引出森林或树转为二叉树的定义。