数结 华中科技大学 计算机学院(8) 200g=27
2001 -- 12 --27 华中科技大学 数据结构计算机学院(8)
6.3遍历二叉树和线索二叉树 6.3.1遍历二叉树 6.3.2建立(生成)二叉树 6.3.3线索二叉树 6.3.4表达式二叉树 表达式二叉树T=(第一操作数)(运算符)(第二操作数) 其中:第一操作数、第二操作数也是表达式二叉树, 分别为表达式二叉树T的左子树和左子树 运算符 第一操作数第二操作数 左二叉树 右二叉树 表达式二叉树
6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 建立(生成)二叉树 6.3.3 线索二叉树 6.3.4 表达式二叉树 表达式二叉树T = (第一操作数) (运算符) (第二操作数) 其中：第一操作数、第二操作数也是表达式二叉树， 分别为表达式二叉树T的左子树和左子树 运算符 第一操作数 左二叉树 第二操作数 右二叉树 表达式二叉树
例表达式:A+B*C一D/(E一F) A)(* B 表达式二叉树 ●前序遍历:-+A米BC/D-EF 前缀表示,前缀表达式,波兰式 ●中序遍历:A+B*C-D/(E-F) 中缀表示,中缀表达式 ●后序遍历:ABC*+DEF-/ 后缀表示,后缀表达式,逆波兰式
例 表达式： A + B * C - D /（E - F） - + / A * D - B C E F ● 前序遍历：- + A * B C / D - E F 前缀表示,前缀表达式,波兰式 ● 中序遍历: A + B * C - D /( E - F ) 中缀表示,中缀表达式 ● 后序遍历: A B C * + D E F - / - 后缀表示,后缀表达式，逆波兰式 表达式二叉树
6.3.5中序遍历序列和前(或后)序序列确定唯一棵二叉树 由前序序列: ADEBC 和(或)后序序列: EDCBA 不能确定唯一棵二叉树 B ①D C(E( 例1.给定二叉树T的 T2 中序序列: BACDEGE 前序序列: EABCD FG 如何求二叉树T? B B, A, C, D)(G,F
6.3.5 中序遍历序列和前(或后)序序列确定唯一棵二叉树 B A C D E T1 B A C D E 例1. 给定二叉树T的 T2 中序序列：B A C D E G F 前序序列：E A B C D F G 如何求二叉树T？ 由前序序列：A D E B C 和(或)后序序列：E D C B A 不能确定唯一棵二叉树 E B,A,C,D G,F E A F B C G D
6.3.5中序遍历序列和前(或后)序序列确定唯一棵二叉树 例2.给定二叉树T的 后序序列: BGHECAJIFD 中序序列: BACGEHDIJF 如何求二叉树T? B AC G,E H
6.3.5 中序遍历序列和前(或后)序序列确定唯一棵二叉树 例2. 给定二叉树T的 后序序列：B G H E C A J I F D 中序序列：B A C G E H D I J F 如何求二叉树T？ D B,A,C G,E,H I,J,F
6.3.5中序遍历序列和前(或后)序序列确定唯一棵二叉树 例2.给定二叉树T的 后序序列: BGHECAJIFD 中序序列: BACGEHDIJF 如何求二叉树T? B AC G,E H 二叉树T
6.3.5 中序遍历序列和前(或后)序序列确定唯一棵二叉树 例2. 给定二叉树T的 后序序列：B G H E C A J I F D 中序序列：B A C G E H D I J F 如何求二叉树T？ D B,A,C G,E,H I,J,F D A F B C I E G H J 二叉树T
6.3.6中序遍历非递归算法 ≯递归算法简明精炼,但效率较低,实际应用中常使用 非递归; 某些高级语言不支持递归; 非递归算法思想: (1)设置一个栈S存放所经过的根结点(指针)信息; 初始化S (2)第一次访问到根结点并不访问,而是入栈 (3)中序遍历它的左子树,左子树遍历结束后,第二 次遇到根结点,就将根结点(指针)退栈,并且访问 根结点;然后中序遍历它的右子树 (4)当需要退栈时,如果栈为空则结束
6.3.6 中序遍历非递归算法 ➢ 递归算法简明精炼，但效率较低，实际应用中常使用 非递归； ➢ 某些高级语言不支持递归； ➢ 非递归算法思想： （1）设置一个栈S存放所经过的根结点（指针）信息； 初始化S； （2）第一次访问到根结点并不访问，而是入栈； （3）中序遍历它的左子树，左子树遍历结束后，第二 次遇到根结点，就将根结点（指针）退栈，并且访问 根结点；然后中序遍历它的右子树。 （4） 当需要退栈时，如果栈为空则结束
C根进栈 A D)(E A 根进栈 根进栈 B t B C DBA t=NULL,表示D的左子 树遍历结束
A B C D E t A A B C D E t B A A B C D E t D B A A B C D E t=NULL,表示D的左子 树遍历结束 根进栈 根进栈 根进栈
D 退栈→t,访问D, B (B t-> rchild→t B ①E t=NULL,表示D的左子 t=NULL,表示B的左子 树遍历结束 树遍历结束 退栈→t,访问B A 根进栈 A t-> rchild→t E B A DB t=NULL,表示E的左子 树遍历结束
D B A A B C D E 退栈➔t，访问D， t->rchild➔t B A A B C D E t=NULL,表示B的左子 树遍历结束 退栈➔t，访问B， t->rchild➔t E A A B C D E A B C A D E t 根进栈 t=NULL,表示E的左子 树遍历结束 D D B t=NULL,表示D的左子 树遍历结束
退栈→t,访问E, E (B t-> rchild→t B t=NULL,表示E的左子 t=NULL,表示A的左子 树遍历结束 树遍历结束 退栈→t,访问A, A 根进栈 A t-> rchild→t B DBE t=NULL,表示C的左子 树遍历结束
E A A B C D E 退栈➔t，访问E， t->rchild➔t A A B C D E t=NULL,表示A的左子 树遍历结束 退栈➔t，访问A， t->rchild➔t C A B C D E A B C D E t 根进栈 t=NULL,表示C的左子 树遍历结束 D B E D B E A t=NULL,表示E的左子 树遍历结束