名师精编优秀教案安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称数据结构教学对象新华软工教材数据结构（ C语言）授课内容第六章树和二叉树课 时2 教学目的与要求了解树、森林的定义；掌握二叉树的定义、性质、存储结构；掌握二叉树的遍历、树和森林的存储，哈夫曼树的应用重点、难点重点 ：二叉树相关操作难点： 二叉树的三种遍历课型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务一、树的有关概念前言：树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用；树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象的表示出来等等。一、树的概念树形结构是一种重要的非线性结构，讨论的是层次和分支关系。树是n 个结点的有限集合，在任一棵非空树中：（1）有且仅有一个称为根的结点。（2）其余结点可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 31 页名师精编优秀教案教学过程设计(续表 ) 树是递归结构，在树的定义中又用到了树的概念例：上面的图是一棵树T=A, B, C, D, E, F, G, H, I, J，K，L，M A 是根，其余结点可以划分为3 个互不相交的集合：T1=B, E, F，K，L , T2=C, G , T3=D, H, I, J ，M 这些集合中的每一集合都本身又是一棵树，它们是A 的子树。例如对于 T11，B 是根，其余结点可以划分为2 个互不相交的集合：T11=E，K，L ，T12=F ，T11,T12 是 B 的子树。从逻辑结构看：1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。二、树的应用1、树可表示具有分枝结构关系的对象例 1家族族谱例 2单位行政机构的组织关系2、树是常用的数据组织形式有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例 3 计算机的文件系统不论是 DOS 文件系统还是 window 文件系统，所有的文件是用树的形式来组织的。J I A C B D H G F E K L M 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 31 页名师精编优秀教案教学过程设计(续表 ) 三、树的表示1）图示表示2）二元组表示3）嵌套集合表示4）凹入表示法（类似书的目录）四、树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；双亲结点： B 结点是 A 结点的孩子，则 A 结点是 B 结点的双亲；兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；祖先结点 : 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；树的深度：树中最大的结点层结点的度：结点子树的个数树的度：树中最大的结点度。叶子结点：也叫终端结点，是度为0 的结点；分枝结点：度不为0 的结点；有序树：子树有序的树，如：家族树；无序树：不考虑子树的顺序；森林；互不相交的树集合；森林和树之间的联系是：一棵树去掉根，其子树构成一个森林；一个森林增加一个根结点成为树。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 31 页名师精编优秀教案复习思考题作业上机任务案例分析：例 1家族族谱例 2单位行政机构的组织关系参考文献课后记（或归纳小结）本章主要介绍树的定义，日常应用，树的概念；为以后的二叉树学习带来好的理解精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 31 页名师精编优秀教案安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称数据结构教学对象新华软工教材数据结构（ C语言）授课内容第六章树和二叉树课 时2 教学目的与要求了解树、森林的定义；掌握二叉树的定义、性质、存储结构；掌握二叉树的遍历、树和森林的存储，哈夫曼树的应用重点、难点重点 ：二叉树相关操作难点： 二叉树的三种遍历课型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务一、树的有关概念（续）复习上一次的内容，然后提出问学生，接着从上一次内容进入今天新的课程，让课程内容的完整性五、树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：1）initiate (T); T 树的初始化，包括建树。2） root (T); 求 T 树的根。3）parent (T , x ): 求 T 树中 x 结点的双亲结点。4）Child (T, x, i )： 求 T 树中 x 结点的第i 个孩子结点。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 31 页名师精编优秀教案教学过程设计(续表 ) 5）right_sibling (T, x ): 求 T 树中 x 结点的右兄弟6）insert_Child (y, i, x ): 将根为 x 的子树置为y 结点的第i 个孩子7） del_child (x, i); 删除 x 结点的第 i 个孩子8）traverse (T); 遍历 T 树。按某个次序依次访问树中每一个结点，并使每个结点都被 访问且只被访问一次。9）clear (T); 置空 T 树任务二、二叉 树树是一种分枝结构的对象， 在树的概念中， 对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树二叉树一、二叉树的概念二叉树： 或为空树，或由根及两颗不相交的左子树、 右子树构成， 并且左、右子树本身也是二叉树。说明1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2; 2）左、右子树不能颠倒 有序树 ; 3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念; 二、二叉树的基本形态(a) 空树(b) 仅有根(c) 右子树空(d) 左、右子树均在(e) 左子树空三、应用举例AFGEDCB精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 31 页名师精编优秀教案教学过程设计(续表 ) 例 1 可以用二叉树表示表达式a+b*(c-d)-e/f 例 2 双人比赛的所有可能的结局开局连赢两局或五局三胜四、 二叉树性质性质 1 在二叉树的第 i 层上最多有 2i-1个结点性质 2 深度为 k 的二叉树最多有2k-1 个结点性质 3 设二叉树叶子结点数为n0，度为 2 的结点 n2，则 n0 = n2 +1 此三个性质是对任何一棵二叉树都实用的精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 31 页名师精编优秀教案复习思考题作业上机任务案例分析：例 1 ：已知二叉树有 50 个叶子结点，则该二叉树的总结点数是多少 （99）例 2：已知完全二叉树的第七层有8 个结点，则其叶子结点数是（36）参考文献课后记（或归纳小结）本章主要介绍二叉树的定义，二叉树的五种形态、还有它的性质，并举例说明这些性质精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 31 页名师精编优秀教案安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称数据结构教学对象新华软工教材数据结构（ C语言）授课内容第六章树和二叉树课 时2 教学目的与要求了解树、森林的定义；掌握二叉树的定义、性质、存储结构；掌握二叉树的遍历、树和森林的存储，哈夫曼树的应用重点、难点重点 ：二叉树相关操作难点： 二叉树的三种遍历课型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务二、二叉 树（续）复习上一次的内容， 然后提问学生， 接着从上一次内容进入今天新的课程，让课程内容的完整性满二叉树：如果深度为k 的二叉树，有 2k-1 个结点则称为满二叉树。完全二叉树：如果深度为k 的二叉树，有 2k-1 个结点则称为满二叉树；对其中的结点的编号：根的号为1，从上到下，从左到右每个结点依次加1 为其编号且一一对应，称之为完全二叉树。下面是两个关于完全二叉树的性质：性质 4 ：具有 n 个结点的完全二叉树的深度为：trunc(log2 n)+1. trunc(x) 为取整函数。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 31 页名师精编优秀教案教学过程设计(续表 ) 对完全二叉树的结点编号：从上到下，每一层从左到右性质 5：在完全二叉树中编号为i 的结点1）若有左孩子，则左孩编号为2i 2）若有右孩子，则右孩子结点编号为2i+1 3）若有双亲，则双亲结点编号为trunc(i/2) 三二叉树存贮结构1、二叉树的顺序结构满二叉树或完全二叉树的顺序结构：用一组连续的内存单元，按编号顺序依次存储完全二叉树的元素 .例如，用一维数组 bt 存放一棵完全二叉树，将标号为 i 的结点的数据元素存放在分量bti-1 中。存储位置隐含了树中的关系，树中的关系是通过完全二叉树的性质实现的。例如，bt5（i=6)的双亲结点标号是 k=trunc(i/2)=3, 双亲结点所对应的数组分量btk-1=bt2 非完全二叉树的顺序结构：按完全二叉树的形式补齐二叉树所缺少的那些结点，对二叉树结点编号,将二叉树原有的结点按编号存储到内存单元“ 相应” 的位置上。但这种方式对于畸形二叉树，浪费较大空间。2、 二叉链表二叉链表中每个结点包含三个域：数据域、左指针域、右指针域；图见课件Struct node int data; struct node *lch,*rch; ; 注：在含有 n 个结点的二叉链表中有n+1 个空链域，这在线索二叉树中将利用到这些空的链域3、三叉链表三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域Struct node int data; struct node *lch,*rch,*parent; ; 见课件和笔记精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 31 页名师精编优秀教案复习思考题作业上机任务案例分析：例：给一个二叉树画这棵树的顺序存储和二叉链表的存储形式，另给一个顺序的存储形式来画出这棵二叉树参考文献课后记（或归纳小结）本章主要介绍完全二叉树和满二叉树的定义，还有它的两个性质；然后介绍二叉树的存储形式：顺序，二叉链表，三叉链表的形式精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 31 页名师精编优秀教案安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称数据结构教学对象新华软工教材数据结构（ C语言）授课内容第六章树和二叉树课 时2 教学目的与要求了解树、森林的定义；掌握二叉树的定义、性质、存储结构；掌握二叉树的遍历、树和森林的存储，哈夫曼树的应用重点、难点重点 ：二叉树相关操作难点： 二叉树的三种遍历课型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务三、二叉树的遍历复习上一次的内容， 然后提问学生， 接着从上一次内容进入今天新的课程，让课程内容的完整性一、二叉树的遍历方法遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 31 页名师精编优秀教案教学过程设计(续表 ) 令：L：遍历左子树T：访问根结点R：遍历右子树有六种遍历方法：T L R，L T R，L R T，T R L，R T L，R L T 先序遍历（ T L R）若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树 ；例：先序遍历右图所示的二叉树（1）访问根结点 A （2）先序遍历左子树：即按T L R 的顺序遍历左子树（3）先序遍历右子树：即按T L R 的顺序遍历右子树中序遍历（ L T R）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树例：中序遍历右图所示的二叉树（1）中序遍历左子树：即按L T R 的顺序遍历左子树（2）访问根结点 A （3）中序遍历右子树：即按L T R 的顺序遍历右子树后序遍历（ L R T）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点例：后序遍历右图所示的二叉树（1）后序遍历左子树：即按L R T 的顺序遍历左子树（2）后序遍历右子树：即按L R T 的顺序遍历右子树（3）访问根结点 A画一个二叉树然后写出它的先序遍历，中序遍历，后序遍历精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 31 页名师精编优秀教案复习思考题作业上机任务案例分析：例：画一个二叉树然后写出它的先序遍历，中序遍历，后序遍历参考文献课后记（或归纳小结）本章主要介绍二叉树三种遍历方法，先序、中序、后序精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 31 页名师精编优秀教案安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称数据结构教学对象新华软工教材数据结构（ C语言）授课内容第六章树和二叉树课 时2 教学目的与要求了解树、森林的定义；掌握二叉树的定义、性质、存储结构；掌握二叉树的遍历、树和森林的存储，哈夫曼树的应用重点、难点重点 ：二叉树相关操作难点： 二叉树的三种遍历课型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务三、二叉树的遍历复习上一次的内容， 然后提问学生， 接着从上一次内容进入今天新的课程，让课程内容的完整性一、遍历的递归算法先序遍历（ T L R）的定义：若二叉树非空（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；上面先序遍历的定义等价于：若二叉树为空，结束基本项（也叫终止项）若二叉树非空递归项精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 31 页名师精编优秀教案教学过程设计(续表 ) （1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；1、先序遍历递归算法void prev (NODE *root) if (root!=NULL) printf(“%d,”, root-data)；prev(root-lch); prev(root-rch); 先序序列为+ * a b c / d e 称为前缀表达式2、中序遍历递归算法void mid (NODE *root) if (root!=NULL) prev(root-lch); printf(“%d,”, root-data)；prev(root-rch); 中序序列为a * b c+ d / e 称为中缀表达式3、 后序遍历递归算法void prev (NODE *root) if (root!=NULL) prev(root-lch); prev(root-rch); printf(“%d,”, root-data)； 后序序列为a b c * d e / + 称为后缀表达式精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 31 页名师精编优秀教案教学过程设计(续表 ) 三、 二叉树遍历的非递归算法递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，效率不高，故有时考虑非递归算法。1、先序遍历（ T L R）的非递归算法 。对每个结点，在访问完后，沿其左链一直访问下来，直到左链为空，这时，所有已被访问过的结点进栈。然后结点出栈，对于每个出栈结点，即表示该结点和其左子树已被访问结束，应该访问该结点的右子树。（1）当前指针指向根结点。（2）打印当前结点，当前指针指向其左孩子并进栈，重复（2） ，直到左孩子为 NULL （3）依次退栈，将当前指针指向右孩子（4）若栈非空或当前指针非NULL ，执行（ 2） ；否则结束。先序遍历的非递归算法void prev (NODE *root) NODE *p, *nodeMAX; int top=0; p=root; do while( p!=NULL) printf(“%d,”, root-data) ; nodetop=p;top+; p=p-lch; if (top0) top - -; p=nodetop; p=p-rch; while(top0|p!=NULL); 2、先序遍历（ T L R ）的非递归算法。中序遍历的非递归算法void min (NODE *root) NODE *p, *nodeMAX; int top=0; p=root; do while( p!=NULL) nodetop=p;top+;p=p-lch; if (top0) top - -; p=nodetop; printf(“%d,”, root-data) ; p=p-rch; while(top0|p!=NULL); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 31 页名师精编优秀教案复习思考题作业上机任务案例分析：例：画递归图，例见笔记参考文献课后记（或归纳小结）本章主要介绍二叉树三种遍历方法，先序、中序、后序的递归的算法和非递归的算法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 31 页名师精编优秀教案课程名称数据结构教学对象新华软工教材数据结构（ C语言）授课内容第六章树和二叉树课 时2 教学目的与要求了解树、森林的定义；掌握二叉树的定义、性质、存储结构；掌握二叉树的遍历、树和森林的存储，哈夫曼树的应用重点、难点重点 ：二叉树相关操作难点： 二叉树的三种遍历课型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务四、树和森林（续）4、孩子兄弟表示法用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和右边下一个兄弟结点。struct node char data; struct node *son, * brother; ; 这种形式的存储和前面介绍的二叉链表存储二叉树的形式是一样，所以在这里就可以通过这种存储方法作为中间量，可以让我们树转换二叉树二、树与二叉树的转换二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 31 页名师精编优秀教案安徽新华电脑专修学院课堂教学教案（电脑应用课使用）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 31 页名师精编优秀教案教学过程设计(续表 ) 二叉树之间的转换。树与二叉树转换方法：用例子说明：如何把一棵树转换成二叉树四、森林：树的集合将森林中树的根看成兄弟， 可用树孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；从树的二叉链表示的定义可知,任何一棵和树对应的二叉树 ,其右子树必为空。所以只要将森林中所有树的根结点视为兄弟，即将各个树转换为二叉树；再按森林中树的次序，依次将后一个树作为前一棵树的右子树，并将第一棵树的根作为目标树的根，就可以将森林转换为二叉树。转换规则：若 F = T1，T2，T3，Tn 是森林，则B（F）=root,LB,RB （1）若 F 为空，即 n=0，则 B(F)为空树。（2）若 F 非空，则 B（F）的根是 T1 的根，其左子树为LB，是从 T1 根结点的子树森林 F1=T11，T12，T1m 转换而成的二叉树； 其右子树为 RB，是从除 T1 外的森林 F =T2 ，T3，Tn 转换而成的二叉树；二叉树还原为森林转换规则：若 B（F）=root,LB,RB 是一棵二叉树，则转换为森林F = T1，T2，Tn 的规则为（1）若 B 为空，则F 为空树。（2）若 B 非空，则F 第一棵树 T1 的根是二叉树的根， T1 中根结点的子森林 F1 是由 B 的左子树 LB 转换而成的森林， F 中除 T1 外其余树组成的森林 F =T2 ，T3，Tn 是由 B（F）的右子树 RB 转换转换而成的；用例子说明如何把一棵树转换成二叉树，再者如何把森林转换成二叉树，然后再来逆转树根结点X 的第一个孩子结点X 紧邻的右兄弟二叉树根结点X 的左孩子结点X 的右孩子精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 31 页名师精编优秀教案复习思考题作业上机任务案例分析：例：用例子说明如何把一棵树转换成二叉树，再者如何把森林转换成二叉树，然后再来逆转参考文献课后记（或归纳小结）本章主要介绍树和二叉树的转换，森林和二叉树的转换等等精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 31 页名师精编优秀教案安徽新华电脑专修学院课堂教学教案（电脑应用课使用）课程名称数据结构教学对象新华软工教材数据结构（ C语言）授课内容第六章树和二叉树课 时2 教学目的与要求了解树、森林的定义；掌握二叉树的定义、性质、存储结构；掌握二叉树的遍历、树和森林的存储，哈夫曼树的应用重点、难点重点 ：二叉树相关操作难点： 二叉树的三种遍历课型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务四、树和森林（续）4、孩子兄弟表示法用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和右边下一个兄弟结点。struct node char data; struct node *son, * brother; ; 这种形式的存储和前面介绍的二叉链表存储二叉树的形式是一样，所以在这里就可以通过这种存储方法作为中间量，可以让我们树转换二叉树二、树与二叉树的转换二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 31 页名师精编优秀教案教学过程设计(续表 ) 二叉树之间的转换。树与二叉树转换方法：用例子说明：如何把一棵树转换成二叉树四、森林：树的集合将森林中树的根看成兄弟， 可用树孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；从树的二叉链表示的定义可知,任何一棵和树对应的二叉树 ,其右子树必为空。所以只要将森林中所有树的根结点视为兄弟，即将各个树转换为二叉树；再按森林中树的次序，依次将后一个树作为前一棵树的右子树，并将第一棵树的根作为目标树的根，就可以将森林转换为二叉树。转换规则：若 F = T1，T2，T3，Tn 是森林，则B（F）=root,LB,RB （1）若 F 为空，即 n=0，则 B(F)为空树。（2）若 F 非空，则 B（F）的根是 T1 的根，其左子树为LB，是从 T1 根结点的子树森林 F1=T11，T12，T1m 转换而成的二叉树； 其右子树为 RB，是从除 T1 外的森林 F =T2 ，T3，Tn 转换而成的二叉树；二叉树还原为森林转换规则：若 B（F）=root,LB,RB 是一棵二叉树，则转换为森林F = T1，T2，Tn 的规则为（1）若 B 为空，则F 为空树。（2）若 B 非空，则F 第一棵树 T1 的根是二叉树的根， T1 中根结点的子森林 F1 是由 B 的左子树 LB 转换而成的森林， F 中除 T1 外其余树组成的森林 F =T2 ，T3，Tn 是由 B（F）的右子树 RB 转换转换而成的；用例子说明如何把一棵树转换成二叉树，再者如何把森林转换成二叉树，然后再来逆转树根结点X 的第一个孩子结点X 紧邻的右兄弟二叉树根结点X 的左孩子结点X 的右孩子精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页，共 31 页名师精编优秀教案复习思考题作业上机任务案例分析：例：用例子说明如何把一棵树转换成二叉树，再者如何把森林转换成二叉树，然后再来逆转参考文献课后记（或归纳小结）本章主要介绍树和二叉树的转换，森林和二叉树的转换等等精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 25 页，共 31 页名师精编优秀教案课程名称数据结构教学对象新华软工教材数据结构（ C语言）授课内容第六章树和二叉树课 时2 教学目的与要求了解树、森林的定义；掌握二叉树的定义、性质、存储结构；掌握二叉树的遍历、树和森林的存储，哈夫曼树的应用重点、难点重点 ：二叉树相关操作难点： 二叉树的三种遍历课型电脑理论教学方法投影、讨论、板书精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 26 页，共 31 页名师精编优秀教案安徽新华电脑专修学院课堂教学教案（电脑应用课使用）教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务五、树的应用（哈夫曼树以及应用）一、哈夫曼树的概念路径：从一个结点到另一个结点之间的若干个分支路径长度 ：路径上的分支数目称为路径长度；结点的路径长度 ：从根到该结点的路径长度树的路径长度 ：树中所有叶子结点的路径长度之和；一般记为PL。在结点数相同的条件下，完全二叉树是路径最短的二叉树。结点的权 ：根据应用的需要可以给树的结点赋权值；结点的带权路径长度 ：从根到该结点的路径长度与该结点权的乘积；树的带权路径长度 =树中所有叶子结点的带权路径之和；通常记作WPL= wi Li 哈夫曼树 ：假设有 n 个权值 (w1 , w2 , , wn )，构造有 n 个叶子结点的严格二叉树， 每个叶子结点有一个wi 作为它的权值。 则带权路径长度最小的严格二叉树称为哈夫曼树。用例子说明，哈夫曼树优点精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 27 页，共 31 页名师精编优秀教案教学过程设计(续表 ) 二、应用举例在求得某些判定问题时，利用哈夫曼树获得最佳判定算法。例编制一个将百分制转换成五分制的程序。最直观的方法是利用if 语句来的实现。可用二叉树描述判定过程。设有 10000个百分制分数要转换，设学生成绩在5 个等级以上的分布如下059：0.05；6069：0.15；7079：0.40；8089：0.3；90100：0.1 按图的判定过程 : 见课件图转换一个分数所需的比较次数= 从根到对应结点的路径长度转换 10000个分数所需的总比较次数= 10000 (0.05 1+0.15 2+0.4 3+0.3 4+0.1 4）三、哈夫曼树的构造构造哈夫曼树的步骤：1根据给定的 n 个权值 ，构造 n 棵只有一个根结点的二叉树，n 个权值分别是这些二叉树根结点的权。设F 是由这 n 棵二叉树构成的集合2在 F 中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值 =左、右子树根结点权值之和；3从 F 中删除这两颗树，并将新树加入F；4重复 2、3，直到 F 中只含一颗树为止；用例说明四、哈夫曼编码在进行数据通讯时， 涉及数据编码问题。 所谓数据编码就是数据与二进制字符串的转换。例如：邮局发电报：原文电文（二进制字符串）原文例要传输的原文为 ABACCDA 等长编码A：00 B：01 C：10 D：11 发送方：将 ABACCDA 转换成00010010101100 接收方：将00010010101100 还原为ABACCDA 不等长编码A：0 B：00 C：1 D：01 发送方：将 ABACCDA 转换成000011010 接收方： 000011010 转换成注：A 的编码是 B 的前缀AAAACCDA BBCCDA 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 28 页，共 31 页名师精编优秀教案教学过程设计(续表 ) 前缀编码：任何字符编码不是其它字符编码的前缀设A：0 B：110 C：10 D：111 发送方：将 ABACCDA 转换成0110010101110 总长度是 13 所得的译码是唯一的可利用二叉树设计前缀编码：例 ：某通讯系统只使用8 种字符 a、b、c、d、e、f、g、h，其使用频率分别为 0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11，利用二叉树设计一种不等长编码：1）构造以a、b、c、d、e、f、g、h 为叶子结点的二叉树；2）将该二叉树所有左分枝标记1，所有右分枝标记0；3） 从根到叶子结点路径上标记作为叶子结点所对应字符的编码；a: 0110 b: 10 c: 1110 d: 1111 e: 110 f: 00 g: 0111 h: 010构造以字符使用频率作为权值的哈夫曼树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 29 页，共 31 页名师精编优秀教案复习思考题作业上机任务案例分析：例：用例子说明如何构造一棵哈夫曼树参考文献课后记（或归纳小结）本章主要介绍树的应用哈夫曼树，它的定义，还有相关概念和它的应用等精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 30 页，共 31 页名师精编优秀教案精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 31 页，共 31 页