第六章基本检索与周游方法
第六章 基本检索与周游方法
问题描述 许多涉及到二元树、树和图的问题 涉及问题中数据结点的访问和处理 有的问题需要访问结构中所有结点,有的 访问结构的部分结点。 本章介绍的方法将适用于树、二元树,有 些方法可以用于图、树、二元树
• 问题描述 • 许多涉及到二元树、树和图的问题 • 涉及问题中数据结点的访问和处理 • 有的问题需要访问结构中所有结点，有的 访问结构的部分结点。 • 本章介绍的方法将适用于树、二元树，有 些方法可以用于图 、树、二元树
61一般方法 1检索与周游 检索:以某种方法检查给定的数据对象,找出满足 某些给定性质的结点的过程称为检索 周游:当检索过程必须检索到数据对象的每一个结 点时,则该检索过程称为周游 访问结点:当算法对一个结点的信息段进行处理时, 称该结点被访问。 结点被访问可以是结点被打印、或作某种处理
6.1 一般方法 1.检索与周游 检索：以某种方法检查给定的数据对象，找出满足 某些给定性质的结点的过程称为检索 周游：当检索过程必须检索到数据对象的每一个结 点时，则该检索过程称为周游 访问结点：当算法对一个结点的信息段进行处理时， 称该结点被访问。 结点被访问可以是结点被打印、或作某种处理
2.二元树周游(遍历) )周游次序 在二元树的周游中,以D、L、R分别代表访问结点 的信息段、访问左子树、访问右子树。则可能的顺序有: ★LDR:中根次序周游(中根遍历) ★LRD:后根次序周游(后根遍历) ★DLR:先根次序周游(先根遍历) ★RDL:逆中根次序周游 ★RLD:逆后根次序周游 ★DRL:逆先根次序周游
2. 二元树周游（遍历） 1）周游次序 在二元树的周游中，以D、L、R分别代表访问结点 的信息段、访问左子树、访问右子树。则可能的顺序有： ★ LDR：中根次序周游（中根遍历） ★ LRD：后根次序周游（后根遍历） ★ DLR：先根次序周游（先根遍历） ★ RDL：逆中根次序周游 ★ RLD：逆后根次序周游 ★ DRL：逆先根次序周游
2)二元树周游算法 (1)中根次序周游 算法6.1中根次序周游的递归表示 procedure INORDER T //是一棵二元树。T的每个结点有三个信息 E: LCHILD, DATA, RCHILD// ifT≠0then call INORDER LCHILD T)) call VISITT call INORDER (RCHILD T) endif end Inorder
2）二元树周游算法 ⑴ 中根次序周游 算法6.1 中根次序周游的递归表示 procedure INORDER(T) //T是一棵二元树。T的每个结点有三个信息 段:LCHILD,DATA,RCHILD// if T≠0 then call INORDER(LCHILD(T)) call VISIT(T) call INORDER(RCHILD(T)) endif end INORDER