树，二叉树和森林的遍历
1.树的遍历
1.1层序遍历
1.2先序遍历
1.3后续遍历
1.4总结
其实同二叉树的遍历一样，先序和后序遍历过程中经过的结点路线都一样，只不过是访问该结点的时机不同而已。
| 遍历方式 | 访问时机 |
| 先序遍历 | 第一次经过结点时访问 |
| 后序遍历 | 最后一次经过结点时访问 |
2.二叉树的遍历
2.1先序遍历
2.2中序遍历
2.3后序遍历
2.4总结
先序、中序和后序遍历过程：遍历过程中经过结点的路线一样，只是访问各结点的时机不同。
| 遍历方式 | 访问时机 |
| 先序遍历 | 第一次经过结点时访问 |
| 中序遍历 | 第二次经过结点时访问 |
| 后序遍历 | 最后一次经过结点时访问 |
图中在从入口到出口的曲线上用U、¶ 和r三种符号分别标 记出了先序、中序和后序访问各结点的时刻：
3.森林的遍历
3.1先序遍历
3.2后序遍历
4.树，二叉树和森林遍历方法的对应关系
4.1树和二叉树
4.2二叉树和森林
4.3总结
先序都一样，二叉树的中序对应树与森林的后序遍历。
| 树 | 二叉树 | 森林 |
| 先序遍历 | 先序遍历 | 先序遍历 |
| 后续遍历 | 中序遍历 | 后序遍历 |
5.两种遍历方法确定一颗树
5.1先序和中序
已知二又树的前序遍历序列为ABCDEFG中序遍历序列为CBEDFGA，试图构造该二又树，并且写出后序遍历序列:
1.先序遍历的第一个必定是整个树的根节点，在中序遍历中找到根结点，根结点左边是左子树，右边是右子树。
2.先序遍历中根节点的下一个必定是整个树的左子树的根结点，在中序遍历中找到左子树的根结点，其左边是左子树的左子树，其右边是左子树的右子树。
5.2中序和后序
已知二又树的中序遍历序列为DBEAFHCG后序遍历序列为DEBHFGCA，试图构造该二叉树，并且写出前序遍历序列:
1.后序遍历的最后一个必然是整棵树的根结点，在中序遍历中找到根节点，其左边的所有是左子树，右边的所有是右子树。
2.将左右子树在后续遍历中框出来，左右子树的最后一个就是左右子树的根节点。
原文地址：https://blog.csdn.net/weixin_65866298/article/details/142825448
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！