森林.md

[toc]

树和森林

具有 $n(n\ge 0)$个结点的有限集称为树。
$m(m\ge 0)$ 个互不相交的树的集合称为森林。

树的存储结构

双亲表示法

树的每个结点只有一个双亲，则结点由数据域和双亲域构成的存储方式称为双亲表示法。
数据域存放结点本身信息，双亲域指示本结点的双亲结点在数组中的位置，根节点的双亲域设置为 -1。

双亲表示法的特点：

• 根据结点的双亲域很容易找到其双亲结点，时间复杂度为 $O(1)$；
• 双亲域为 -1 时，表示其为根节点；
• 查找结点的孩子结点不容易，只能通过遍历整个树结构。

孩子表示法

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储称为孩子表示法。 $n$ 个结点由 $n$ 个孩子链表（叶子的孩子链表为空表）；$n$ 个头指针又组成一个线性表，用顺序表存储。

孩子表示法的特点：

• 根据结点的指针域很容易找到其孩子结点，时间复杂度为 $O(1)$；
• 指针域为空的结点为叶子结点；
• 查找结点的双亲结点不容易。

孩子兄弟表示法

用二叉链表作树的存储结构，链表中每个结点包含数据域、左指针域、右指针域的存储结构称为孩子兄弟表示法。

• 左指针指向第一个孩子结点；
• 右指针指向下一个兄弟结点。

存储示例：

孩子兄弟表示法特点：

• 若要访问结点 $p$ 的第 $i$ 个孩子：从左指针域找到第一个孩子结点；并沿着孩子结点的右指针域寻找 $i-1$ 次便能找到对应的孩子。
• 查找结点的孩子容易，找双亲难。

树和二叉树的转换

树与二叉树都可以使用链式存储，且树与二叉树的二叉链表是相同的，仅是指针域的含义不同，所以树和二叉树可以相互转换。

树转换成二叉树

树转换成二叉树步骤：(兄弟相连留长子)

• 加线：在兄弟之间加一连线
• 抹线：对每个结点，除其左孩子外，去除其与其他孩子之间的关系
• 旋转：以树的根结点为轴心，将树顺时针转45度

二叉树转换成树

二叉树转换成树步骤：(左孩右右连双亲)

• 加线：若 $p$ 结点是双亲结点的左孩子，则将 $p$ 的右孩子，右孩子的右孩子..沿分支找到的所有右孩子，都与 $p$ 的双亲用线连起来
• 抹线：去除原二叉树中双亲与右孩子之间的连线
• 调整：将结点按层次排列，形成树结构

森林和二叉树的转换

森林与二叉树转换时，把森林中第二棵树的根节点看成第一棵树根节点的兄弟结点即可。

森林转二叉树的步骤：(树变二叉根相连)

• 将各棵树分别转换成二叉树
• 将每棵树的根结点用线相连
• 以第一棵树的根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

二叉树转森林的步骤：(去掉全部右孩先，孤立二叉再还原)

• 抹线：将二叉树中根结点与其右孩子连线，沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
• 还原：将孤立的二叉树还原成树

树和森林的遍历

树遍历的方法：

• 先根遍历：若树不为空，访问根结点；依次先根遍历各棵子树。
• 后根遍历：若树不为空，依次遍历各棵子树；访问根结点。
• 层次遍历：若树不为空，自上而下、自左至右访问树中每个结点。

森林可以分为三个部分：森林中第一棵树的根结点、森林中第一棵树的子树森林、森林中其他树构成的森林

森林遍历的方法：

1. 先序遍历：若树不为空，依次从左到右对森林中的每一棵树进行先根遍历
2. 中序遍历：若树不为空，依次从左到右对森林中的每一棵树进行后根遍历

参考

• 《数据结构(C语言版)》 严魏敏、吴伟民著
• 《数据结构(第3版)》 刘大有等著