数结 华中科技大学 计算机学院(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