数据结构之树（3）

一、森林和树的转换

重要！

树->二叉树

由于孩子兄弟链式存储和二叉树链式存储本质相同，故树可转换为二叉树。

森林->二叉树

森林：m棵互不相交的树的集合

森林->树 树->二叉树

森林中各个树的根节点之间视为兄弟关系

二、树的遍历

先根遍历

先访问根节点，在先根遍历下一棵子树

A  B  C  D

A (B E F) (C G) (D H I J)

A B E K F C G D H I J

后根遍历

先后跟遍历下一棵子树，尽头的时候再访问根结点并回溯

((K E) F B) (G C) (H I J D) A

先根遍历和后根遍历均是深度优先遍历

附：

森林的遍历（此部分在刷题的时候较少遇到，所以略过，详见5.4_2_树和森林的遍历_哔哩哔哩_bilibili）

其实本质就是森林转二叉树，再用二叉树的知识解决。

先序遍历

访问森林中第一棵树的根节点

先序遍历第一棵树中根节点的子树森林

先序遍历除去第一棵树之后剩余树构成的森林

效果等同于依次对各个树进行先根遍历

依次对二叉树的先序遍历

中序遍历