文章目录

• 5.4 树、森林
• 5.4.1 树的存储结构
• 1. 双亲表示法（顺序存储）
• 2. 孩子表示法（顺序+链式存储）
• 3. 孩子兄弟表示法（链式存储）
• 5.4.2 树、森林与二叉树的转换
• 1. 树与二叉树的相互转换
• 2. 森林与二叉树的相互转换
• 3. 小结
• 5.4.3 树和森林的遍历
• 1. 树的遍历
• 2. 森林的遍历
• 3. 小结

5.4 树、森林

5.4.1 树的存储结构

树的存储方式有很多种，既可以采用顺序存储结构，又可以采用链式存储结构，但无论采用何种存储方式，都要求唯一地反映树中各结点之间的逻辑关系，这里介绍3种常用的存储结构。

1. 双亲表示法（顺序存储）

存储结构描述如下：

增/删/查：

如果用方案一处理，当要对树进行遍历时，碰到空数据会导致遍历很慢。所以用方案二更优。

小结：
该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但求结点的孩子时需要遍历整个结构。

2. 孩子表示法（顺序+链式存储）

存储结构描述如下：
小结：
孩子表示法是将每个结点的孩子结点都用单链表链接起来形成的一个线性结构，这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表的指针域。

3. 孩子兄弟表示法（链式存储）

以二叉链表作为树的存储结构。
存储结构描述如下：

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

5.4.2 树、森林与二叉树的转换

1. 树与二叉树的相互转换

2. 森林与二叉树的相互转换

3. 小结

树与二叉树相互转换本质是：用二叉链表存储树。
森林与二叉树相互转换本质是： 用二叉链表存储森林。

5.4.3 树和森林的遍历

1. 树的遍历

2. 森林的遍历

3. 小结