[科普中国]-遍历序列- · 科普中国网

简介

在计算机科学中，所谓遍历(Traversal)，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历序列是指沿着某条搜索路线访问序列中的元素，不同的遍历方式，其访问序列中元素的顺序是不一样的，并且和序列的有关性质有关，例如一个给定序列的子序列是从给定序列中去除一些元素，而不改变其他元素之间相对位置而得到的。在数据结构中，应用遍历序列最多的结构是树和图。

二叉树的遍历序列二叉树的定义二叉树(BinaryTree)是一种树型结构，它的特点是每个节点至多只有两棵子树（即二叉树中不存在度大于2的节点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。1二叉树的五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空；或左、右子树均为非空的二叉树。

遍历方案从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

（1）访问结点本身(N)，

（2）遍历该结点的左子树(L)，

（3）遍历该结点的右子树(R)。

以上三种操作有六种执行次序：

NLR、LNR、LRN、NRL、RNL、RLN。

前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。

三种遍历的命名根据访问结点操作发生位置命名：

① NLR：前序遍历(PreorderTraversal亦称(先序遍历))

——访问结点的操作发生在遍历其左右子树之前。

② LNR：中序遍历(InorderTraversal)

——访问结点的操作发生在遍历其左右子树之中(间)。

③ LRN：后序遍历(PostorderTraversal)

——访问结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

遍历算法1. 中序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

(1)遍历左子树；

(2)访问根结点；

(3)遍历右子树。

2．先序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

(1) 访问根结点；

(2) 遍历左子树；

(3) 遍历右子树。

3．后序遍历得递归算法定义：

若二叉树非空，则依次执行如下操作：

(1)遍历左子树；

(2)遍历右子树；

(3)访问根结点。

中序遍历的算法实现用二叉链表做为存储结构，中序遍历算法可描述为：

void InOrder(BinTree T)

{ //算法里①~⑥是为了说明执行过程加入的标号

① if(T) { // 如果二叉树非空

② InOrder(T->lchild)；

③ printf("%c"，T->data)； // 访问结点

④ InOrder(T->rchild);

⑤ }

⑥ } // InOrder

图的遍历序列图的定义图(Graph)是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构有着广泛的应用。图G由两个集合V和E组成，记为：

G=(V，E)

其中：

V是顶点的有穷非空集合，

E是V中顶点偶对(称为边)的有穷集。

通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。

深度优先遍历序列对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或简称为DFS序列。

（1）一个图的DFS序列不一定惟一当从某顶点x出发搜索时，若x的邻接点有多个尚未访问过，则我们可任选一个访问之。

（2）源点和存储结构的内容均已确定的图的DFS序列惟一

① 邻接矩阵表示的图确定源点后，DFS序列惟一

DFSM算法中，当从vi出发搜索时，是在邻接矩阵的第i行上从左至右选择下一个未曾访问过的邻接点作为新的出发点，若这样的邻接点多于一个，则选中的总是序号较小的那一个。

②只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列

邻接表作为给定图的存储结构时，其表示不惟一。因为邻接表上边表里的邻接点域的内容与建表时的输入次序相关。因此，只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列。

广度优先遍历序列广度优先遍历的递归定义

设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为：首先访问出发点v，接着依次访问v的所有邻接点w1，w2，…，wt，然后再依次访问与wl，w2，…，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。

若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。

广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。

广度优先搜索过程

在广度优先搜索过程中，设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1，x2，…，xs和y1，y2，…，yt。为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时，这两个顶点相继入队。此后，当x和y相继出队时，我们分别从x和y出发搜索其邻接点x1，x2，…，xs和y1，y2，…，yt，对其中未访者进行访问并将其人队。这种方法是将每个已访问的顶点人队，故保证了每个顶点至多只有一次人队。

广度优先搜索算法

void BFS(ALGraph*G，int k)

{// 以vk为源点对用邻接表表示的图G进行广度优先搜索

int i；

CirQueue Q； //须将队列定义中DataType改为int

EdgeNode *p；

InitQueue(&Q)；//队列初始化

//访问源点vk

printf("visit vertex：%e"，G->adjlist[k].vertex)；

visited[k]=TRUE；

EnQueue(&Q，k)；//vk已访问，将其人队。（实际上是将其序号人队）

while(!QueueEmpty(&Q)){//队非空则执行

i=DeQueue(&Q)； //相当于vi出队

p=G->adjlist[i].firstedge； //取vi的边表头指针

while(p){//依次搜索vi的邻接点vj(令p->adjvex=j)

if(!visited[p->adivex]){ //若vj未访问过

printf("visitvertex：%c"，C->adjlistlp->adjvex].vertex)； //访问vj

visited[p->adjvex]=TRUE；

EnQueue(&Q，p->adjvex)；//访问过的vj人队

}//endif

p=p->next；//找vi的下一邻接点

}//endwhile

}//end of BFS