【数据结构】树与森林

目录

树的存储方法

双亲表示法

孩子表示法

孩子兄弟表示法

树、森林与二叉树的转换

树转换成二叉树

森林转换成二叉树

二叉树转换成森林

树与森林的遍历

树的遍历

森林的遍历

---

树的存储方法

双亲表示法

这种存储结构采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置，根结点下标为0，其伪指针域为-1。

孩子表示法

孩子表示法是将每个结点的孩子结点视为一个线性表，且以单链表作为存储结构，则n个结点就有n个孩子链表(叶结点的孩子链表为空表)。而n个头指针又组成一个线性表，为便于查找，可采用顺序存储结构。

孩子兄弟表示法

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容:结点值、指向结点第一个孩子结点的指针，以及指向结点下一个兄弟结点的指针，其中左指针指向第一个孩子，右指针指向第一个兄弟。

孩子兄弟表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等,但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便。

孩子兄弟表示法代码如下：

typedef struct CSNode{int data;struct CSNode *firstchild, *nextsibling;
}CSNode,*CSTree;

树、森林与二叉树的转换

树转换成二叉树

树转换为二叉树的规则是：每个节点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟。这种规则也被称为“左孩子右兄弟”表示法。由于根节点在树中没有兄弟，因此树转换得到的二叉树的根节点没有右子树。

将树转换为二叉树的画法可以按照以下步骤进行：

1. 在兄弟节点之间加连线：对于树中的每个节点，将其所有子节点（即兄弟节点）之间用线连接起来。
2. 保留第一个孩子的连线，删除其他孩子的连线：对于每个节点，只保留它与第一个孩子的连线，而删除与其他子节点的连线。
3.顺时针旋转 45°：以树的根节点为轴心，将整个结构顺时针旋转 45°，使得转换后的二叉树符合“左孩子右兄弟”的规则。

示例如下：

森林转换成二叉树

将森林转换为二叉树的规则与树转换为二叉树类似，具体步骤如下：

1. 先将森林中的每棵树分别转换为二叉树，转换规则遵循“左孩子右兄弟”原则，即每个节点的左指针指向其第一个孩子，右指针指向其相邻的右兄弟。
2. 连接各二叉树：由于每棵树转换为二叉树后，其右子树必定为空，因此可以将森林中第二棵树的根节点视为第一棵树根节点的右兄弟，即将第二棵树对应的二叉树作为第一棵二叉树根的右子树；同理，将第三棵树对应的二叉树作为第二棵二叉树根的右子树，依次类推，最终将整个森林连接成一棵二叉树。

二叉树转换成森林

二叉树转换为森林的规则如下：

1. 确定第一棵树：如果二叉树非空，那么二叉树的根节点及其左子树对应森林中的第一棵树。因此，需要将根节点的右链断开。
2. 递归处理剩余部分：断开右链后，二叉树根的右子树可以看作是由森林中除第一棵树之外的其余树转换而来的二叉树。对这个右子树重复上述操作，即继续断开右链，提取下一颗树，直到最后只剩下一棵没有右子树的二叉树为止。
3.转换为树：将每棵提取出的二叉树依次转换为树。最终，这些树组合起来就是原森林。

二叉树转换为树或森林的过程是唯一的。

树与森林的遍历

树的遍历

树的遍历是指按照某种顺序访问树中的每个节点，并且每个节点只被访问一次。主要的遍历方式有两种：

先根遍历

1. 如果树非空，先访问根节点。
2. 然后依次遍历根节点的每棵子树，在遍历子树时仍然按照“先根后子树”的规则进行。
3. 先根遍历的序列与这棵树转换为二叉树后的先序遍历序列相同。

后根遍历：

1. 如果树非空，先依次遍历根节点的每棵子树，在遍历子树时仍然按照“先子树后根”的规则进行。
2. 遍历完所有子树后，再访问根节点。
3. 后根遍历的序列与这棵树转换为二叉树后的中序遍历序列相同。

森林的遍历

森林的遍历方法基于森林和树的递归定义，主要有两种遍历方式：

先序遍历森林：

1. 如果森林非空，先访问森林中第一棵树的根节点。
2. 然后先序遍历第一棵树中根节点的子树森林（即第一棵树的子树部分）。
3. 最后，先序遍历除去第一棵树之后剩余的树构成的森林。

中序遍历森林：

1. 如果森林非空，先中序遍历森林中第一棵树的根节点的子树森林（即第一棵树的子树部分）。
2. 然后访问第一棵树的根节点。
3. 最后，中序遍历除去第一棵树之后剩余的树构成的森林。