数据结构第6章 树和二叉树3.ppt

根据遍历序列还原二叉树 根据各种遍历的特点，从相应的遍历序列中得到二叉树的结构信息。 根据各种遍历方法的定义可知： 只有已知二叉树的先序序列和中序序列，或者已知二叉树的后序序列和中序序列才能唯一确定一棵二叉树， 由先序序列和后序序列不能唯一确定一棵二叉树。 ----------------------------------------------------------------------------------------------------------------------------------------------------------------- 习题2：已知一棵二叉树的中序序列为ABCDEFGHIJK，先序序列为EBADCFHGIKJ，求对应的二叉树。 先序：EBADCFHGIKJ ==根：E 根据根结点来划分中序序列 中序：ABCDEFGHIJK==ABCD+E+FGHIJK 由左右子树的结点集合来划分先序序列 ==先序：E+BADC+FHGIKJ 如图（a） 分别对左右子树运用相同的方法分解出根和其左右子树的结点集合。 先序：E+BADC+FHGIKJ 中序：ABCDEFGHIJK 依次递归，如图(b)、(c)。 由两个遍历序列构造二叉树 已知一棵二叉树的先序序列和中序序列，构造该二叉树的过程如下： ⑴ 根据先序序列的第一个元素建立根结点； ⑵ 在中序序列中找到该元素，确定根结点的左右子树的中序序列； ⑶在先序序列中确定左右子树的先序序列； ⑷由左子树的先序序列和中序序列建立左子树； ⑸由右子树的先序序列和 中序序列建立右子树。 Ⅲ. 建立二叉链表存储结构 三、线索二叉树 问题的提出 通过遍历二叉树可得到结点的一个线性序列，在遍历序列中，就存在结点的前驱和后继； 但在二叉树上只能找到结点的左孩子和右孩子，结点的前驱和后继只有在遍历过程中才能得到； 那么，能否通过结点的两个链域查找出任一结点的前驱和后继？ n个结点共有2n个链域，其中:n+1个空链域，n-1个孩子指针域； 用空链域来存放结点的前驱或后继信息。 线索链表 结点结构 对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化 根据遍历的不同要求，线索二叉树分为 先序线索二叉树 中序线索二叉树 后序线索二叉树 线索树及线索链表的画法 在二叉树或二叉链表中，若左孩子为空，则画出它的直接前驱，若右孩子为空，则画出它的直接后继，左右孩子不为空时，不需画前驱和后继。 这样就得到了线索二叉树或线索二叉链表。 * 第六章 树和二叉树 6.1 树的类型定义 6.2 二叉树的类型定义和实现 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 Huffman树与Huffman编码 一棵二叉树由根结点、根结点的左子树（简称左子树）和 根结点的右子树（简称右子树）三部分组成。 先左后右和先右后左相互对称，约定先左后右的顺序。二叉树可以有三条有哪些信誉好的足球投注网站路径： ⑴先(根)序遍历：根?左子树?右子树 ⑵中(根)序遍历：左子树?根?右子树 ⑶后(根)序遍历：左子树?右子树?根 一、遍历二叉树 练习1： B E C F G D H B E F C G D H F E B G C H D F E G H D C B 先序序列： 中序序列： 后序序列： 二叉树的先序遍历序列 左子树的先序遍历序列 右子树的先序遍历序列 二叉树的根 二叉树的后序遍历序列 左子树的后序遍历序列 右子树的后序遍历序列 二叉树的根 二叉树的中序遍历序列 左子树的中序遍历序列 右子树的中序遍历序列 二叉树的根 E 先序:BADC 中序:ABCD 先序:FHGIKJ 中序:FGHIJK (a) E B F A 先序:DC 中序:CD 先序:HGIKJ 中序:GHIJK (b) E B F A 先序:IKJ 中序:IJK (c) D C H G E B F A 先序:KJ 中序:JK (d) D C H G I K E B F A (e) D C H G I J 习题3： 已知二叉树的先序遍历序列为：AEFCGDB，中序遍历序列为：FEAGCBD，则它的后序序列必是 。 F E G B D C A A E C F G D B 习题4 ： 二叉树的先序序列为ABCDEF，中序序列为CBAEDF，画出该二叉树。 习题5 ： 已知二叉树的先序遍历序列为:ABECDFGHIJ，中序遍历序列为:EBCDAFHIGJ，画出这棵二叉树。 习题6 ： 已知二叉树的中序序列BDCEAFHG , 后序序列DECBHGFA，请画出这棵二叉树。 后序： DECBHGFA ==根：A 根据根结点来划分中序序列 中序： BDCEAFHG ==BDCE+