层次遍历和先序遍历区别，先序遍历和中序遍历

今天小编mail为大家分享的生活小常识，希望能够帮助到大家！

先序遍历序列，先序遍历这个很多人还不知道,现在让我们一起来看看吧！

1、先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。

2、首先访问根结点然后遍历左子树，最后遍历右子树。

3、在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。

4、例如，下图所示二叉树的遍历结果是：ABDECF2、后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。

5、即：若二叉树为空则结束返回，否则：（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点如右图所示二叉树后序遍历结果：DEBFCA已知前序遍历和中序遍历，就能确定后序遍历。

6、扩展资料：图的遍历算法主要有两种，一种是按照深度优先的顺序展开遍历的算法，也就是深度优先遍历；另一种是按照宽度优先的顺序展开遍历的算法，也就是宽度优先遍历。

7、宽度优先遍历是沿着图的深度遍历图的所有节点，每次遍历都会沿着当前节点的邻接点遍历，直到所有点全部遍历完成。

8、如果当前节点的所有邻接点都遍历过了，则回溯到上一个节点，重复这一过程一直到已访问从源节点可达的所有节点为止。

9、如果还存在没有被访问的节点，则选择其中一个节点作为源节点并重复以上过程，直到所有节点都被访问为止。

10、利用图的深度优先搜索可以获得很多额外的信息，也可以解决很多图论的问题。

11、宽度优先遍历又名广度优先遍历。

12、通过沿着图的宽度遍历图的节点，如果所有节点均被访问，算法随即终止。

13、宽度优先遍历的实现一般需要一个队列来辅助完成。

14、 宽度优先遍历和深度优先遍历一样也是一种盲目的遍历方法。

15、也就是说，宽度遍历算法并不使用经验法则算法， 并不考虑结果的可能地址，只是彻底地遍历整张图，直到找到结果为止。

16、图的遍历问题分为四类：遍历完所有的边而不能有重复，即所谓“欧拉路径问题”（又名一笔画问题）；2、遍历完所有的顶点而没有重复，即所谓“哈密顿路径问题”。

17、3、遍历完所有的边而可以有重复，即所谓“中国邮递员问题”；4、遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。

18、对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。

19、第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密顿图的性质。

20、参考资料来源：百度百科-遍历参考资料来源：百度百科-后序遍历参考资料来源：百度百科-先序遍历。

Luochuanren.Com洛川人-综合信息门户网站，涵盖生活常识、美食、创业、体育、旅游、家居、汽车、财经、互联网、科技、房产、教育等资讯。