数据结构课件第六章3.ppt

第6章 树和二叉树（Tree Binary Tree） 6.3 遍历二叉树和线索二叉树 例：【 2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 线索二叉树的生成（递归算法见教材P134-135） 6.4 树和森林 6.4.1 树和森林与二叉树的转换 树转二叉树举例： 讨论2：二叉树怎样还原为树？ 森林转二叉树举例：（用法二，森林直接变兄弟，再转为二叉树） 讨论4：二叉树如何还原为森林？ 6.4.2 树和森林的存储方式 例如： 6.4.3 树和森林的遍历 森林的遍历 附：二叉树若干典型算法（习题课） 附2：层次遍历算法(需要利用队列) 严题集6.47 ④ 附3：判别给定二叉树是否为完全二叉树 严题集6.49 ④ 附4：中序遍历的非递归算法(或称迭代算法)见教材P131 * 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用 二叉树的运算 6.3.1 遍历二叉树 遍历——指按某条有哪些信誉好的足球投注网站路线遍访每个结点且不重复。 常用的有先序、中序和后序遍历，还有层次遍历。 Traversing Binary Tree 6.3.2 线索二叉树 用二叉链表法存储包含n个结点的二叉树，结点的指针区域中会有n+1个空指针。 可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。 Threaded Binary Tree 28 25 40 55 60 33 08 54 解:因为中序遍历序列是：55 40 25 60 28 08 33 54 对应线索树应当按此规律连线，即在原二叉树中添加虚线。 NIL NIL NIL和NULL的值都是0,区别何在？ 在Delphi中NIL用来标记空指针，Null用来表示空的Variant型变量或是ASCII码为0的字符，比如用于标记字符串结束。 在C/C++中定义的宏NULL不加区别的包括了以上两种含义。 可见Object Pascal的语法要比C/C++严谨得多 设计技巧：依某种顺序遍历二叉树，对每个结点p，判断其左指针是否为空，以及其前驱结点的右指针是否为空。 每次只修改前驱结点的右指针（后继）和本结点的左指针（前驱），参见算法6.6。 线索二叉树的遍历（无需堆栈） 难点：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。 6.4.1 树和森林与二叉树的转换 6.4.2 树和森林的存储方式 6.4.3 树和森林的遍历 转换步骤： step1: 将树中同一结点的兄弟相连; 加线 抹线 旋转 讨论1：树如何转为二叉树？ 孩子—兄弟表示法 step2: 保留结点的最左孩子连线，删除其它孩子连线； step3: 将同一孩子的连线绕左孩子旋转45度角。 方法：加线—抹线—旋转 a b e i d f h g c a b e i d f h g c 兄弟相连 长兄为父 孩子靠左 特点是？ 根结点没有右孩子！ a b e i d f h g c 要点：逆操作，把所有右孩子变为兄弟！ a b d e f h g i c 法一： ① 各森林先各自转为二叉树； ② 依次连到前一个二叉树的右子树上。 讨论3：森林如何转为二叉树？ 即F={T1, T2, …,Tm} B={root, LB, RB} 法二：森林直接变兄弟，再转为二叉树 （参见教材P138图6.17，两种方法都有转换示意图） 法一和法二得到的二叉树是完全相同的、惟一的。 A B C D E F G H J I A B C D E F G H J I A B C D E F G H J I 兄弟相连 长兄为父 头树为根 孩子靠左 A A B C D E F G H J I 要点：把最右边的子树变为森林，其余右子树变为兄弟 即B={root, LB, RB} F={T1, T2, …,Tm} A B C D E F G H J I E F A B C D G H J I 树有三种常用存储方式： ①双亲表示法 ②孩子表示法 ③孩子—兄弟表示法 nextsibling data firstchild 指向左孩子 指向右兄弟 问：树→二叉树的“连线—抹线—旋转” 如何由计算机自动实现？ 答：用“左孩子右兄弟”表示法来存储即可。 存储的过程就是树转换为二叉树的过程！ a b e c d f h g b a c e d f g h 树的遍历 例如： a b d e c 先根序列： 后根序列： a b c d e b d c e a 深度优先遍历（先根、后根） 广度优先遍历（层次） 先根遍历 访问根结点； 依次先根遍历根结点的每棵子