Traverse树遍历.pdf

二叉树的抽象数据类型 二叉树的抽象数据类型  ADT BinaryTree { ADT BinaryTree {  数据对象 D: D 是具有相同特性的数据元素的 数据对象 D: D 是具有相同特性的数据元素的 集合。 集合。  数据关系 R: 数据关系 R:  基本操作集合 P: PreOrderTraverse(T): 先序 基本操作集合 P: InOrderTraverse(T): 中序 Traverse(T) Traverse(T) PostOrderTraverse(T): 后序 LevelOrderTraverse(T): 层 序 关键算法：遍历，其他算法都 遍历 根植于本算法思想来实现。 二叉树的遍历 (Traversing) 二叉树的遍历 (Traversing)  遍历：按某种有哪些信誉好的足球投注网站路径访问二叉树的每个结 遍历：按某种有哪些信誉好的足球投注网站路径访问二叉树的每个结 点，而且每个结点仅被访问一次。 点，而且每个结点仅被访问一次。  访问：对结点的各种操作，如输出结点中的 访问：对结点的各种操作，如输出结点中的 数据，修改结点中的数据等。 数据，修改结点中的数据等。  遍历是各种数据结构最基本的操作，许多其 遍历是各种数据结构最基本的操作，许多其 他的操作可以在遍历上实现。 他的操作可以在遍历上实现。 二叉树的遍历方法 二叉树的遍历方法  二叉树由根、左子树、右子树三部分组成，定义 二叉树由根、左子树、右子树三部分组成，定义 为 D 、 L 、 R 为 D 、 L 、 R  D 、 L 、 R 的组合定义了六种可能的遍历方案 D 、 L 、 R 的组合定义了六种可能的遍历方案 ： ：  DLR, DRL DLR, DRL  LDR, RDL LDR, RDL  LRD, RLD LRD, RLD  若限定先左后右，则有三种实现方案： 若限定先左后右，则有三种实现方案： DLR LDR LRD D D D 先序/ 根遍历 中序/ 根遍历 先 中 后序/ 根遍历 后  先序遍历  中序遍历  后序遍历  先序遍历算法框架： 若二叉树为空，则空操作；否则 A (1) 访问根结点； (2) 先序遍历左子树； B C (3) 先序遍历右子树； D E F G 先序遍历序列 :DLR 先序遍历序列 :DLR A B D E H I K C F G J J A B D E H I K