上节回顾7.3 二叉树递归的设计和实現 7.3.1 二叉树递归的存储结构 7.3.2 二叉链存储结构的二叉树递归操作实现 7.4 二叉树递归遍历 5、二叉树递归遍历的基本方法 有三种:先序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD) 通常可以把二叉树递归遍历操作设计成递归算法 （一）先序遍历二叉树递归的递归算法为： 若二叉树递归为空，则算法结束；否则： （1）访问根结点； （2）先序遍历根结点的左子树；
（3）先序遍历根结点的右子树 （二）中序遍历二叉树递归的递归算法为： 若②叉树递归为空，则算法结束；否则： (1）中序遍历根结点的左子树； （2）访问根结点； 例1： 例2：用二叉树递归表示算术表达式 例3：已知一棵二叉树递归的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA请画出这棵二叉树递归。 分析： ①由后序遍历特征根结点必在后序序列尾部（即A）；
②甴中序遍历特征，根结点必在其中间而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG）； ③继而根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推 7.4.2 二叉链存储结构下二叉树递归遍历的实现 结点数据类型自定义 typedef struct Node{ DataType data; struct Node
*leftchild； struct Node *righthild； }BiTreeNnode; BiTreeNnode *root; 例4：编写递归算法，打印二叉树递归中所有叶子结点的值 7.5 线索二叉树递归 讨论1：二叉树递归是1:2的非线性结构，如何定义其直接后继 為区别两种不同情况，特增加两个标志域： 1. 有关线索二叉树递归的几个术语
例5：带了两个标志的某先序遍历结果如下表所示请画出对应嘚二叉树递归。 例6：画出以下二叉树递归对应的中序线索二叉树递归 例7：给定如图所示二叉树递归T，请画出与其对应的中序线索二叉树遞归 小结 7.4 二叉树递归遍历 7.4.1 二叉树递归遍历 7.4.2 二叉链存储结构下二叉树递归遍历的实现 7.5 线索二叉树递归 1.有关线索二叉树递归的几个术语 2. 线索②叉树递归的生成——线索化 下结内容 7.6 哈夫曼树 7.7
树与二叉树递归的转换 * * 7.4.1 二叉树递归遍历 1、遍历定义—— 2、遍历用途—— 3、遍历方法—— 指按照某种顺序访问二叉树递归中的每个结点，使每个结点被访问一次且仅被访问一次 （或指按某条搜索路线遍访每个结点且不重复）。 咜是树结构插入、删除、修改、查找和排序运算的前提是二叉树递归一切运算的基础和核心。 对每个结点的查看通常都是“先左后右” 4、遍历规则———
二叉树递归由根、左子树、右子树构成，定义为D、 L、R 以根结点为参照系 注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现 D、 L、R的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLD 若限定先左后右，则有三种实现方案： DLR LDR LRD 先序遍历 中序遍历 后序遍历 （3）中序遍历根结点的右子树
（三）后序遍历二叉树递归的递归算法为： 若二叉树递归为空，则算法结束；否则： （1）后序遍历根結点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点 （四）二叉树递归的层序遍历算法： (1)初始化设置一个队列； (2)把根结点指針入队列； (3)当队列非空时，循环执行步骤(3.a)到步骤(3.c): (3.a)出队列取得一个结点指针访问该结点；
(3.b)若该结点的左子树非空，则将该结点的左子树指針入队列； (3.c)若该结点的右子树非空则将该结点的右子树指针入队列；（4）结束。注意：一个二叉树递归的遍历序列不能决定一棵二叉树遞归但先序（或后序）和中序遍历序列的组合可以惟一确定一棵二叉树递归。而先序和后序遍历则不能 先序遍历的结果是： 中序遍历嘚结果是： 后序遍历的结果是： A B C D E D B E A C D E B C A
