Question

遍历是什么意思

Answer 1

遍历指沿着某条搜索路线。

所谓遍历（Traversal），是指沿着某条搜索路线，依次对树（或图）中每个节点均做一次访问。访问结点所做的操作依赖于具体的应用问题，具体的访问操作可能是检查节点的值、更新节点的值等。遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次。

不同的遍历方式，其访问节点的顺序是不一样的。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。当然遍历的概念也适合于多元素集合的情况，如数组。

深度优先遍历含义

深度优先遍历是沿着图的深度遍历图的所有节点，每次遍历都会沿着当前节点的邻接点遍历，直到所有点全部遍历完成。如果当前节点的所有邻接点都遍历过了，则回溯到上一个节点，重复这一过程一直到已访问从源节点可达的所有节点为止。

如果还存在没有被访问的节点，则选择其中一个节点作为源节点并重复以上过程，直到所有节点都被访问为止。利用图的深度优先搜索可以获得很多额外的信息，也可以解决很多图论的问题。