树，森林的遍历，以及其与二叉树遍历之间的关系-Toy模板网

这篇具有很好参考价值的文章主要介绍了树，森林的遍历，以及其与二叉树遍历之间的关系。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

树和森林的的遍历

树的遍历

先根遍历

以下列树为演示

树，森林的遍历，以及其与二叉树遍历之间的关系,数据结构,算法,数据结构

首先将树转化成二叉树（孩子兄弟表示法：就是每个节点的左边连着它的左孩子，右边连自己右边的第一个兄弟）

树，森林的遍历，以及其与二叉树遍历之间的关系,数据结构,算法,数据结构

然后把转化为的二叉树进行先序遍历，中序遍历

进行先序遍历的序列为:ABEFCDGIH

进行中序遍历的序列为：EFBCIGHDA

如果树非空，则先访问根节点，然后按从左向右的顺序，先跟遍历根节点的每一棵子树。（像是对树进行类似二叉树的先序遍历）

树的先根遍历顺序与该树对应的二叉树的先序遍历顺序相同。

然后根据树的先根遍历就是二叉树的先序遍历，得出树的先根遍历为：ABEFCDGIH

后根遍历

如果树非空，则按从左向右的顺序，后根遍历根节点的每一棵子树，然后访问根节点。（像是对树进行类似二叉树的后序遍历步骤）

根据树的后根遍历就是二叉树的中序遍历得出树的后根遍历为：EFBCIGHDA

森林的遍历

森林的遍历操作包括先序遍历和中序遍历两种方式。

拿如下森林举例：

树，森林的遍历，以及其与二叉树遍历之间的关系,数据结构,算法,数据结构

首先把森林转化为二叉树，同样使用孩子兄弟表示法，节点的左孩子是树的左孩子，节点的右孩子是左孩子的右边相邻的兄弟。

转化为二叉树如下图：

树，森林的遍历，以及其与二叉树遍历之间的关系,数据结构,算法,数据结构

先序遍历

如果森林非空，则先访问第一棵树的根节点，先序遍历第一棵树的根节点的所有子树森林；

先序遍历除第一棵树之外，剩余树构成的森林。（像是对森林进行类似二叉树的先序遍历步骤）

森林的先序遍历顺序与该森林对应的二叉树的先序遍历顺序相同。

中序遍历

如果森林非空，则中序遍历第一棵树的根节点的子树森林，然后访问第一棵树的根节点；

中序遍历除第一棵树之外，剩余树构成的森林。（像是对森林进行类似二叉树的后序遍历步骤）

森林的中序遍历顺序与该森林对应的二叉树的中序遍历顺序相同。

总结：

树，森林，二叉树的遍历关系

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

总之，如果是不会直接看出是如何遍历的，都可以先把树，森林等转化成二叉树，根据树的先根遍历对应二叉树的先序遍历，树的后根遍历对应二叉树的中序遍历；森林的先序遍历对应二叉树的先序遍历，森林的中序遍历对应二叉树的中序遍历来解答。文章来源地址https://www.toymoban.com/news/detail-628381.html

到了这里，关于树，森林的遍历，以及其与二叉树遍历之间的关系的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！