Question

什么叫遍历算法(最好有例子)

Answer 1

遍历算法：所谓遍历(Traversal)，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。当然遍历的概念也适合于多元素集合的情况，如数组。

遍历算法概念延伸： 

图遍历：图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。

举例：

遍历二叉树搜索路线：

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：⑴访问结点本身（N），⑵遍历该结点的左子树（L），⑶遍历该结点的右子树（R）。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三种次序与后三种次序对称。

遍历二叉树的执行踪迹三种递归遍历算法的搜索路线相同（如下图虚线所示）。具体线路为：从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。

Answer 2

1 2 3 4 85 6 7这个叫做八数码，就相当于以前玩的拼图板，只有空格的位置可以移动。也就是说对于现在这个状态，可以有4种下一个状态，如果我们把这个状态叫做一个结点的话，那我们把它可以到达的那种状态叫做他的子节点，这样一直下去就可以形成一个网状结构。如果初始状态为2 3 45 61 7 8，而你要到达上面说的那一种状态，这时就需要从该节点开始一直往下搜索它的子节点，一直往下找直到找到目的节点，这时就形成了一条路径。这就叫做搜索，搜索一般是不完全的遍历，遍历就是找把这个网中所有节点都访问一次；遍历算法有深度优先和广度优先两种，广度优先就是把该节点的所有子节点都访问完才访问下一节点，深度优先就是沿着一个方向直到这一方向走不下去才回过头去走下一节点。