基本检索与周游方法讲述.pptxVIP

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