基本检索与周游方法.pptx

基本检索与周游方法对于问题涉及到二叉树、树和图的处理，要求确定满足某一性质的结点集合，就需要检索的方式来进行，当这种检索必须包括对检索的数据对象的每一个结点进行检查时，就称为周游。回顾：线性表的遍历 二叉树的周游（遍历） 所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 遍历的结果：产生一个关于结点的线性序列。 设访问根结点记作 D 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 先序DLR DRL逆先序 中序LDR RDL逆中序 后序LRD RLD 逆后序 遍历规则———若限定先左后右，则有三种实现方案： DLR LDR LRD先 (根)序遍历中 (根)序遍历后(根)序遍历 注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。 A B CD E例1：A B D E CD B E A CD E B C A先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根先序遍历二叉树的递归算法void PreOrderTraverse(BiTree T){ if (T){ printf(%c,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); }}中序遍历二叉树的递归算法void InOrderTraverse(BiTree T){ if (T) { InOrderTraverse(T-lchild); printf(%c,T-data); InOrderTraverse(T-rchild); }}后序遍历二叉树的递归算法void PostOrderTraverse(BiTree T){ if (T) { PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c,T-data); }}练习A前序序列： ABDGCEFH 中序序列： DGBAECHF 后序序列： GDBEHFCA B CD E FG H那么对于图，我们怎样进行遍历呢？图的深度优先遍历图的广度优先遍历V1V2V4V3V5V6 图的存储结构图的特点：非线性结构（m :n ）顺序存储结构：无！（多个顶点，无序可言）但可用数组描述元素间关系。链式存储结构：可用多重链表设计为邻接矩阵重点介绍：邻接矩阵(数组)表示法邻接表(链式)表示法v2v1Av3v4v4v5一、邻接矩阵（数组）表示法用二维数组分别表示数据元素的（顶点）的信息和（弧）的信息。设图 A = (V, E) 有 n 个顶点，则图的用于表示数据元素之间关系的邻接矩阵是一个二维数组 A.Edge[n][n]，定义为：无权图例1（无向图邻接矩阵）：顶点表：（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 001 0 1 01 0 1 010 1 01 11 01 0101 1 1 0A.Edge =v2v1Av3v4v4v5顶点表：例1：（ v1 v2 v3 v4 v5 ）v1v2v3v4v501 0 1 01 0 1 010 1 01 11 01 0101 1 1 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 001 0 1 01 0 1 010 1 01 11 01 0101 1 1 0A.Edge =分析1：无向图的邻接矩阵是对称的；分析2：对于无向图来说，顶点i 的度＝第 i 行 (列) 中1 的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。v2v1Av3v4例2 ：有向图的邻接矩阵顶点表：( v1 v2 v3 v4 )邻接矩阵：01 1 00 0 0 00 0 01 1 0 0 0 0 0 0 00 0 0