下载掌阅APP，畅读海量书库
立即打开
普通树可以转化为二叉树，转化步骤如下：
（1）在普通树的兄弟结点之间加一条线，使兄弟结点互连，如图2-115所示。
图2-115 兄弟结点间加一条线示意图
（2）对于树中的每个结点，只保留其与第一孩子结点的连线，删除结点与其他孩子结点之间的连线，如图2-116所示。
图2-116 每个结点只保留与第一个孩子结点的连线示意图
（3）调整树的层次结构。以树的根结点为轴心，将整棵树旋转一定的角度，使树结构层次分明，如图2-117所示。
图2-117 调整树的层次结构示意图
森林由多棵树组成。森林可以转化为二叉树，转化步骤如下：
（1）将森林中的每棵树转化为二叉树，如图2-118所示。
图2-118 森林中的每棵树转化为二叉树示意图
（2）保持第一棵不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来，如图2-119所示。
图2-119 依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子示意图
（3）调整树的层次结构。以树的根结点为轴心，将整棵树旋转一定的角度，使树结构层次分明，如图2-120所示。
图2-120 调整树的层次结构示意图
树的遍历分为以下两种：
（1）先根遍历。先访问树的根结点，再依次先根遍历根的每棵子树。
（2）后根遍历。先依次遍历每棵子树，再访问根结点。
图2-121所示的树，先根遍历的结果为ABEFCGDHIJ，后根遍历的结果为EFBGCHIJDA。
图2-121 普通树示意图
森林的遍历也分为先跟遍历和后根遍历，其实就是按照树的先根遍历和后根遍历依次访问森林的每一棵树。
在图2-122所示的森林中，森林的先根遍历结果为ABCDEFGHI，森林的后根遍历结果为BCDAFEHIG。
图2-122 森林示意图
（1）普通树与二叉树间的转换。
（2）森林与二叉树间的转换。
（3）树的遍历方式。
（4）森林的遍历方式。