【数据结构与算法】树的存储,森林 详解
树的几种存贮结构(双亲表示法、孩子表示法、孩子兄弟表示法)的优缺点，各自适应的运算。
-
双亲表示法：
- 优点：方便查找双亲及其祖先结点
- 缺点：
- 查找孩子和兄弟结点比较费事
- 未表示出结点之间的先后次序
- 适应的运算：查找节点的双亲，合并两棵树等。
-
孩子表示法（孩子链表表示法）：
- 优点：
- 方便查找孩子及其子孙结点
- 能表示出结点之间的先后次序
- 缺点：
- 查找结点的双亲及祖先费事
- 查找结点的兄弟也费事
- 适应的运算：查找节点的孩子，插入节点等。
- 优点：
-
孩子兄弟表示法（二叉链表表示法）：
- 优点：
- 便于实现树的各种操作，如查找孩子、子孙或兄弟结点
- 能表示出结点之间的先后次序
- 缺点：找结点的双亲及祖先比较费事
- 适应的运算：查找节点的兄弟，查找节点的孩子，插入节点，删除节点等。
- 优点：
哪种存贮结构可将森林转为二叉树。
可以使用"左孩子右兄弟"表示法将森林转换为二叉树。在这种表示法中，每个节点有两个指针，一个指向其第一个孩子（左孩子），另一个指向其下一个兄弟（右兄弟）。
这种方法将森林中的每棵树转换为二叉树，其中树的根是二叉树的根，树的子树（森林）转换为二叉树的左子树，而森林的其余部分转换为二叉树的右子树。
此种结构各域的注释。
每个节点包含以下字段：
- 数据域：存储节点的数据。
- 左孩子指针：指向节点的第一个孩子。如果节点是叶子节点，那么这个指针为空。
- 右兄弟指针：指向节点的下一个兄弟。如果节点是同一父节点的最后一个孩子，那么这个指针为空。
说明在这个结构中怎样找到森林的n棵树。
要找到森林的n棵树，可以从根节点开始，沿着"右兄弟"指针遍历n-1次。具体步骤如下：
- 从根节点开始。
- 沿着"右兄弟"指针移动n-1次。每次移动都将你带到下一棵树的根节点。
- 停止移动后，你将位于第n棵树的根节点。
这种方法的前提是，森林的所有树都在同一层级，并且根节点的"右兄弟"指针指向下一棵树的根节点。如果森林的树不在同一层级，或者根节点的"右兄弟"指针不指向下一棵树的根节点，那么这种方法可能无法正确找到第n棵树。