湖北工业大学：《数据结构》第7章 树和二叉树（Tree & Binary Tree）（3/5）

上节回顾 7.3二叉树的设计和实现 7.3.1二叉树的存储结构 7.3.2二叉链存储结构的二叉树操作实现

1 上节回顾 7.3 二叉树的设计和实现 7.3.1 二叉树的存储结构 7.3.2 二叉链存储结构的二叉树操作实现

7.4二叉树遍历 74.1二叉树遍历 1、遍历定义指按照某种顺序访问二叉树中的每个结点, 使每个结点被访问一次且仅被访问一次。 (或指按某条搜索路线遍访每个结点且不 重复) 2、遍历用途是树结构插入删除、修改、耷找和排 序运算的前提,是二叉树一切运算的基础 和核心。 3、遍历方法对每个结点的查看通常都是“先左后右

2 7.4 二叉树遍历 7.4.1 二叉树遍历 1、遍历定义—— 2、遍历用途—— 3、遍历方法—— 指按照某种顺序访问二叉树中的每个结点， 使每个结点被访问一次且仅被访问一次。 （或指按某条搜索路线遍访每个结点且不 重复）。 它是树结构插入、删除、修改、查找和排 序运算的前提，是二叉树一切运算的基础 和核心。 对每个结点的查看通常都是“先左后右”

4、遍历规则 二又树由根、左子树、右子树构成,定义为D、L、R 令D、L、R的组合定义了六种可能的遍历方案: LDR. LRD. DLR DRL RDL RLD 令若限定先左后右,则有三种实现方案 DLR LDR LRD 先序遍历中序遍历 后序遍历 注:“先、中、层的意思是指访问的结点D是先于子树出 现还是后于子树出现。 以根结点为参照系

3 4、遍历规则——— 二叉树由根、左子树、右子树构成，定义为D、L、R 以根结点为参照系 注：“先、中、后”的意思是指访问的结点D是先于子树出 现还是后于子树出现。 ❖ D、 L、R的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLD ❖ 若限定先左后右，则有三种实现方案： DLR LDR LRD 先序遍历 中序遍历 后序遍历

5、二叉树遍历的基本方法 有三种:先序遍历(LR)、中序遍历LDR)、后序遍历(LRD 通常可以把二叉树遍历操作设计成递归算法。 (一)先序遍历二叉树的递归算法为: 若二叉树为空,则算法结束;否则: (1)访问根结点; (2)先序遍历根结点的左子树; (3)先序遍历根结点的右子树。 (二)中序遍历二叉树的递归算法为 若二叉树为空,则算法结束;否则: (1)中序遍历根结点的左子树; (2)访问根结点;

4 5、二叉树遍历的基本方法 有三种:先序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD) 通常可以把二叉树遍历操作设计成递归算法。 （一）先序遍历二叉树的递归算法为： 若二叉树为空，则算法结束；否则： （1）访问根结点； （2）先序遍历根结点的左子树； （3）先序遍历根结点的右子树。 （二）中序遍历二叉树的递归算法为： 若二叉树为空，则算法结束；否则： (1）中序遍历根结点的左子树； （2）访问根结点；

(3)中序遍历根结点的右子树 (三)后序遍历二叉树的递归算法为: 若二叉树为空,则算法结束;否则 (1)后序遍历根结点的左子树; (2)后序遍历根结点的右子树; (3)访问根结点。 (四)二叉树的层序遍历算法: (1)初始化设置一个队列; (2)把根结点指针入队列; (3)当队列非空时,循环执行步骤(3.a)到步骤(3.c):

5 （3）中序遍历根结点的右子树。 （三）后序遍历二叉树的递归算法为： 若二叉树为空，则算法结束；否则： （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点。 （四）二叉树的层序遍历算法： (1)初始化设置一个队列； (2)把根结点指针入队列； (3)当队列非空时，循环执行步骤(3.a)到步骤(3.c):

3.a)出队列取得一个结点指针,访问该结点; (3.b)若该结点的左子树非空,则将该结点的左子树指针入 队列; (3.c)若该结点的右子树非空,则将该结点的右子树指针入 队列; (4)结束。 注意:一个二又树的遍历序列不能决定一棵二叉树,但先 序(或后序)和中序遍历序列的组合可以惟一确定一棵二叉 树。而先序和后序遍历则不能

6 (3.a)出队列取得一个结点指针，访问该结点； (3.b)若该结点的左子树非空，则将该结点的左子树指针入 队列； (3.c)若该结点的右子树非空，则将该结点的右子树指针入 队列； （4）结束。 注意：一个二叉树的遍历序列不能决定一棵二叉树，但先 序（或后序）和中序遍历序列的组合可以惟一确定一棵二叉 树。而先序和后序遍历则不能

例1: 先序遍历的结果是: ABD E O 中序遍历的结果是: D BE AC B 后序遍历的结果是: DEBCA 口诀: DLR一先序遍历,即先根再左再右 LDR一中序遍历,即先左再根再右 LRD一后序遍历,即先左再右再根

7 例1： 先序遍历的结果是： 中序遍历的结果是： 后序遍历的结果是： A B C D E D B E A C D E B C A 口诀： DLR—先序遍历，即先根再左再右 LDR—中序遍历，即先左再根再右 LRD—后序遍历，即先左再右再根 A B D E C

例2:用二叉树表示算术表达式先序遍历结果 +**/abcde 前缀表示法 E 中序遍历结果 A/B *c*d+e D 一中缀表示法 后序遍历结果 AB/CAdre+ 后缀表示法 A B 层次遍历结果 +REd/CaB

8 + * A * / E D C B 先序遍历结果 + * * / A B C D E —前缀表示法 中序遍历结果 A / B * C * D + E —中缀表示法 后序遍历结果 A B / C * D * E + —后缀表示法 层次遍历结果 + * E * D / C A B 例2：用二叉树表示算术表达式

例3:已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG和 DECBHGFA,请画出这棵二叉树 分析: ①由后序遍历特征,根结点必在后序序列尾部(即A); ②由中序遍历特征,根结点必在其中间,而且其左部必 全部是左子树的子孙(即BDCE),其右部必全部是右 子树的子孙(即FHG); ③继而,根据后序中的DECB子树可确定B为A的左孩子, 根据HGE子串可确定F为A的右孩子;以此类推

9 例3：已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 分析： ①由后序遍历特征，根结点必在后序序列尾部（即A）； ②由中序遍历特征，根结点必在其中间，而且其左部必 全部是左子树的子孙（即BDCE），其右部必全部是右 子树的子孙（即FHG）； ③继而，根据后序中的DECB子树可确定B为A的左孩子， 根据HGF子串可确定F为A的右孩子；以此类推

已知中序遍历: BDCEAFHG 已知后序遍历: DECBHGFA B F H (DCE (FHG

10 已知中序遍历：B D C E A F H G 已知后序遍历：D E C B H G F A （B D C E（）D C E） （ F H G） B F G H C D E A