第7-2讲_树的遍历_774807304.pdf

数据结构 第第77--22讲讲 树树的遍历的遍历 清华大学 自动化系 黄双喜黄双喜 博士博士、副教授副教授 huangsx@tsinghua.edu.cn 提纲 • 树的遍历 • 二叉树遍历算法 • 遍历的应用遍历的应用 • 线索二叉树 遍历的概念 所谓树的遍历，就是按某种次序访问树中的结所谓树的遍历，就是按某种次序访问树中的结 点点点点，，，，要求每个结点访问一次且仅访问一次要求每个结点访问一次且仅访问一次要求每个结点访问一次且仅访问一次要求每个结点访问一次且仅访问一次。。。。 树的遍历 线性关系的遍历 ？ ？ ？ ？ 树的遍历 如何确定遍历顺序？ 4 遍历的方法 先根遍历：即先访问树的根结点，然后依次 先根遍历根的每棵子树。 后根遍历：即先依次后根遍历每棵子树，然 后再访问根结点。 牢记一种约定，对于结点的查看都是“先左后右”。 二叉树的遍历 二叉树由根、左子树、右子树构成，定义为： {{DD、、 LL、、R}R} D、 L、R的组合定义了六种可能的遍历方案： LLDDRR, LRLRDD, DDLRLR, DDRLRL, RRDDLL, RLRLDD 若限定先左后右，则有三种实现方案： DLR LDR LRD 先先((根根))序遍历序遍历 中中((根根))序遍历序遍历 后后((根根))序遍历序遍历 “先、中、后”的意思是指访问的结点D是先于子 树出现还是后于子树出现。 先序遍历 定义如下 若二叉树为空，则空操 作;否则 （1）访问根结点 （（22））前序遍历左子树前序遍历左子树;; （3）前序遍历右子树; A B D E G H C F I J 后序遍历 定义如下 若二叉树为空，则空操作； 否则 (1) 后序遍历左子树； (2)(2) 后序遍历右子树后序遍历右子树 ；； (3) 访问根结点。 D G H E B J I F C A 中序遍历 定义如下 若二叉树为空，则空操作； 否则 (1) 中序遍历左子树； (2(2))访问根结点访问根结点。 (3)中序遍历右子树； DBGEHACIJF 不同遍历方法的应用 文件夹删除 企业组织结构描述 (a+b)*((c-d)*e+f) 表达式计算表达式计算 10 算术表达式的计算 •表达式求值是程序设计语言编译中的一个 最基本问题最基本问题。。 •用