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

何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？ 6.8  哈 夫 曼 树 与 哈 夫 曼 编 码 最优树的定义 如何构造最优树 前缀编码 要求 1. 掌握将一棵树转化为二叉树 2. 将一个森林转化为二叉树 A B C D E F G H I J K L A B C D E F K L G H I J B C D E F G H I J K L B C D E F K L G H I J typedef struct CSNode{ Elem data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree; C语言的类型描述: 结点结构: firstchild data nextsibling 森林和二叉树的对应关系 设森林 F = ( T1, T2, …, Tn ); T1 = (root，t11, t12, …, t1m); 二叉树 B =( LBT, Node(root), RBT ); 。。。 T1 T2 T3 T4 Tn T1 T11 T12 T1m 。。。 T1 T11 T12 T1m 。。。 T2 T3 Tn 。。。 由森林转换成二叉树的转换规则为: 若 F = Φ，则 B = Φ； 否则， 由ROOT( T1 )对应得到 Node(root)； 由 (t11, t12, …, t1m ) 对应得到 LBT； 由 (T2, T3,…, Tn ) 对应得到 RBT。 由二叉树转换为森林的转换规则为： 若 B = Φ， 则 F = Φ； 否则， 由Node(root) 对应得到 ROOT( T1 )； 由LBT 对应得到 ( t11, t12, …，t1m)； 由RBT 对应得到 (T2, T3, …, Tn)。 由此，树的各种操作均可对应二叉树的操作来完成。 应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为： 左是孩子，右是兄弟。 6.7 树和森林的遍历 一、树的遍历 二、森林的遍历 三、树的遍历的应用 树的遍历可有三条有哪些信誉好的足球投注网站路径: 按层次遍历: 先根(次序)遍历: 后根(次序)遍历: 若树不空，则先访问根结点，然后依次先根遍历各棵子树。 若树不空，则先依次后根遍历各棵子树，然后访问根结点。 若树不空，则自上而下自左至右访问树中每个结点。 A B C D E F G H I J K 先根遍历时顶点的访问次序： A B E F C D G H I J K 后根遍历时顶点的 访问次序： E F B C I J K H G D A 层次遍历时顶点的访问次序： A B C D E F G H I J K B C D E F G H I J K 1．森林中第一棵树 的根结点； 2．森林中第一棵树 的子树森林； 3．森林中其它树构 成的森林。 森林由三部分构成： 1. 先序遍历 森林的遍历 若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其余树构成的森林。 即：依次从左至右对森林中的每一棵树进行先根遍历。 ２．中序遍历 若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中(除第一棵树之外)其余树构成的森林。 即：依次从左至右对森林中的每一棵树进行后根遍历。 先根遍历 后根遍历 树 二叉树 森林 先序遍历 先序遍历 中序遍历 中序遍历 树的遍历和二叉树遍历的对应关系 ？ 例1. 已知树的前序次序为 abdcegf 中序次序为 bdaegcf 则树为？ a b d c f e g 例2. 已知树的后序次序为 dbgefca 中序次序为 bdaegcf 则树为？ 我们可以利用前序次序和中序次序、后序次序和中序次序 来确定一棵二叉树。 6.5线索二叉树 一、何谓线索