Question

数据结构--树和森林

Answer 1

一、 树的定义：
树(tree)是n(n>0)个节点的有限集，在任意一棵树中，(1)有且仅有一个特定的称为根(root)的节点，(2)当n>1时，其余节点可分为m(m>0)个互不相交的有限集，而每个集合本身又是一棵树，称为根的子树(subtree)。

从上面树的定义中可以看到，这是一个递归的定义，即树的定义中又用到了树的概念。

树具有下面两个特点：
(1) 树的根结点没有前驱结点，除根结点外的其他结点有且只有一个前驱结点
(2) 树中所有结点可以有0个或多个后继结点
根据这两个特点，可以看出下图表示的都不是树。

森林(forest)是m(m≥0)棵互不相交的树的集合。任何一棵树，删除了根结点就变成了森林。

二、 树的存储结构
1、 双亲表示法
树中每个结点都有唯一一个双亲结点，根据这一特性，可以用一组连续的存储空间（一维数组）存储树中的各个结点，数组中每个元素都表示树中的一个结点，数组元素为结构体类型，这个结构体类型由结点本身的数据和结点的双亲在数组中的序号组成。

树的双亲表示法对于寻找双亲和根的操作很方便，但是要求某结点的孩子结点，就需要遍历整个数组，而且也不能反映各兄弟之间的关系，因此找到某结点的兄弟也很困难。

2、 孩子表示法
按如下图所示的形式存储。主体是一个与结点个数一样大小的一维数组，数组的每个元素有两个域，一个域用于存放结点数据，另一个用于存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个为指针域，指向下一个孩子。

孩子表示法中查找双亲很困难，适用于查找孩子的操作。

3、 双亲孩子表示法
双亲孩子表示法是将双亲表示法和孩子表示法结合起来的方法。如下图所示，将各节点的孩子结点组成单链表，用一维数组顺序存储树的结点，数组元素包括结点本身的数据，该结点的孩子结点链表的头指针，存储该结点的双亲在数组中的序号。

4、 孩子兄弟表示法
这种方法的结构体包含：每个结点的数据，指向该结点的第一个孩子结点的指针和指向下一个兄弟结点的指针。

三、 树转换为二叉树

第一步：在树中所有兄弟结点间加一条连线

第四步：调整位置

五、 二叉树转换为树、森林

七、 森林的遍历
森林的遍历分为两种：前序遍历和中序遍历
1、 前序遍历
A. 访问森林中第一棵树的根节点
B. 前序遍历第一棵树的根节点的子树
C. 前序遍历去掉第一棵树后剩余的森林

上图按照前序遍历，结果为：A B C D E F G H J I K

2、 中序遍历
A. 中序遍历第一棵树的根节点的子树
B. 访问森林中第一棵树的根结点
C. 中序遍历去掉第一棵树剩余的森林
上图按照中序遍历，结果为：B A D E F C J H K I G