遍历二叉树(近2学时).ppt

知识回顾x 二叉树: 定义 特点 ADT 形态 性质 存储 6.3 遍历二叉树和线索二叉树 1. 概念与方法 ? 2. 递归算法 ? 3. 两条规则 ? 4. 算术表达式与二叉树 ? 5. 中序遍历的非递归算法 ? 6. 遍历算法的几个递归例子 ? 6.3.1 遍历二叉树 小 结 √ √ √ √ √ 作业 1. 概念与方法 遍历:对数据元素访问并且仅访问一次. 遍历二叉树: 方法一:按层遍历(从上到下,从左到右) 方法二: 约定先左(L)再右(R) DLR DRL LDR LRD RLD RDL 根 D 左 子 树 L 右 子 树 R 先序遍历 中序遍历 后序遍历 模拟过程如 邮递员送信 A B F C D G E ? ? ? ? ? ? ? 第1次遇到门,即送:先序 第2次遇到门,即送:中序 第3次遇到门,即送:后序 (1) 先序遍历 若二叉树为空,空操作;否则: ① 访问根结点 ② 先序遍历左子树 ③ 先序遍历右子树 A B F C D G E (2) 中序遍历 若二叉树为空,空操作;否则: ① 中序遍历左子树 ② 访问根结点 ③ 中序遍历右子树 (3) 后序遍历 若二叉树为空,空操作;否则: ① 后序遍历左子树 ② 后序遍历右子树 ③ 访问根结点 ? 2. 递归算法 二叉链表存储定义 typedef struct BiTNode { char data; struct BiTNode * lchild, * rchild; } BiTNode, * BiTree; (2) 二叉链表的建立(先序序列输入,空树空格表示) BiTree CreatBitree( ) { BiTree T; char ch; scanf(%c,ch); if(ch== ) return(0); else { T=(BiTNode *)malloc(sizeof(BiTNode)); T-data=ch; T-lchild=CreatBitree( ); T-rchild=CreatBitree( ); return(T); } } (3) 二叉链表的遍历 void preorder(BiTree T) { if(T) { printf(%c,T-data); preorder(T-lchild); preorder(T-rchild); } } ? 3. 两条规则 规则1:由前序遍历序列和中序遍历序列可以唯一确定一棵二叉树 如: 规则2:由后序遍历序列和中序遍历序列可以唯一确定一棵二叉树 前序遍历序列+后序遍历序列?? ? 前序遍历序列 A B C D E F G 中序遍历序列 C B E D A F G 构造二叉树 据前序序列知根为A,左右子树如下 A C BE D F G …… A B F C D G E 根据此规则得二叉树? 4. 算术表达式与二叉树 （1）表达式构成 表达式1=(运算数1) 运算符 (运算数2) …… 表达式由多个表达式或运算数等构成 （2）二叉树表示（例） （3）遍历：