《数据结构与算法（C语言） 教案 第04章 树.docx》由会员分享，可在线阅读，更多相关《数据结构与算法（C语言） 教案 第04章 树.docx（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、千锋教育数据结构与算法（C语言篇）教学设计课程名称：数据结构与算法（C语言篇）授语年级：授课学期：教师娓名：2020年03月01日/*后序遍历，参数为指向根结点的指针*/ int after order(btree t *root)/*判断工一个结点是否有左(右)孩子*/if(root = NULL) return 0;/*递归调用，如果有左孩子，输出左孩子的数据*/ if(root-lchild != NULL) after order(root-lchild);/*递归调用，如果有右孩子，输出右孩子的数据*/ if(root-rchild != NULL) after order(root
2、-rchild);/*输出结点的数据*/printf (H%d ”，root-data); return 0;4.层序遍历二叉树的层序遍历可以利用队列的思想，从第一个结点(根结点)开始 入队，然后出队，判断此结点是否有左孩子或右孩子。如果存在那么继续入队, 入队后继续执行之前的步骤。读者可参考3. 6节的链式队列操作函数或例3- 8来测试层序遍历的代码，具体代码参考教材节。整体测试.完全二叉树测试使用创立完全二叉树的功能代码(例4-1),结合先序遍历、中序遍历、 后序遍历的功能代码进行测试，例如代码参考教材4. 3. 4节。根据第96行代码可知，创立一棵完全二叉树，且结点数为10,该二叉 树的
3、逻辑结构如下图。.非完全二叉树测试使用创立非完全二叉树的功能代码(例4-2),结合先序遍历、中序遍 历、后序遍历的功能代码进行测试，例如代码参考教材4. 3. 4节。第二课时(赫夫曼树、特殊的树)7内容回顾.回顾上节内容，引出本课时主题。上节已经介绍了树的定义、树的基本术语、二叉树的概念、满二叉树、 完全二叉树、二叉树的性质、二叉树的存储、二叉树的遍历方式、二叉树的 定义、二叉树的创立和二叉树的遍历，下面将介绍赫夫曼树的概念、赫夫曼 树的原理、构造赫夫曼树、二叉排序树、平衡二叉树、B树、B+树与B*树 和红黑树。1 .明确学习目标(1)能够掌握赫夫曼树的概念(2)能够掌握赫夫曼树的原理(3)能
4、够掌握构造赫夫曼树(4)能够掌握二叉排序树(5)能够掌握平衡二叉树(6)能够掌握B树(7)能够掌握B+树与B*树(8)能够掌握红黑树3知识讲解赫夫曼树的概念赫夫曼树又称为最优二叉树。1952年，美国数学家赫夫曼(David Huffman)创造了一种压缩编码方法，为实现文件压缩，提高数据传输效率 做出了重要贡献。为了纪念他的成就，将他在编码中使用的特殊二叉树称为 赫夫曼树，同时将他的编码方式称为赫夫曼编码。赫夫曼树的原理代表优秀，权值为10对图所示的二叉树进行简化，如下图。在图所示的二叉树中，A代表不及格，B代表及格，C代表中等，D代 表良好，E代表优秀。这些结点对应的值为学生成绩占比。而赫夫
5、曼树的定 义中，树中每个结点的数据域可以存放一个特定的数值来，这个值称为权值。 因此，将学生成绩占比作为结点的权值，得到结点A的权值为5,结点B的 权值为15,结点C的权值为30,结点D的权值为40,结点E的权值为10。在了解赫夫曼树的原理之前，需要先了解关于赫夫曼树的名词解释(结 合图4.23和图4.24) o(1)路径：在一棵树中，从一个结点到另一个结点之间的通路称为路 径。图中，从根结点到结点C的通路就是一条路径。(2)路径长度：一条路径中的分支数目称为路径长度，也就是说，在一 条路径中，每经过一个结点，路径长度加1。图中，根结点到结点C的路径 长度为3,根结点到结点D的路径长度为4。(
6、3)树的路径长度：从根结点到每一个结点的路径长度之和。图4.23 所示的树的路径长度为1 + 1+2+2+3+3+4+4=20,图4.24所示的树的路径长度 为 1+2+3+3+2+1+2+2=16。(3)结点的带权路径长度：从根结点到该结点的路径长度与该结点的 权值的乘积。(4)结点的带权路径长度：树中所有叶结点的带权路径长度之和。假设有n个权值w 1 ,w2,wn ,构造一棵有n个叶结点的二叉树， 每个叶结点的权值为wk,每个叶结点的的路径长度为1k ,那么该树的带权 路径长度记作WPL=wklko其中带权路径长度WPL最小的二叉树称为 赫夫曼树。图所示的二叉树的 WPL值为5义1 +15
7、 X 2+30义3+40义4+10义4=325。图 所示的二叉树的 WPL值为5X3+15X3+30X2+40X2+10X2=220o如果学 生成绩例如中有10000人，按照图4.23所示二叉树的判断方法，需要执行 32500次比拟，而按照图4.24所示二叉树的判断方法，需要执行22000次比 较。很明显，采用第二种方式效率要比第一种高很多。构造赫夫曼树442节已经介绍了赫夫曼树的原理，接下来将讨论如何构建赫夫曼树。 在构建赫夫曼树时，想要使树的带权路径长度最小，只需要遵循一个原那么， 权值越大的结点离树根越近。假设有6个带权的结点，权值分别为9、12、6、3、5、15,将这些结点 按照从小到
8、大顺序进行排列，如下图。选出图中两个权值最小的结点，将这两个结点组成一个新的二叉树，且 新二叉树的根结点的权值为左右孩子权值的和。如下图。在未组成树的剩余结点中选出权值最小的结点与二叉树合并，形成新的 二叉树，如下图。此时新二叉树的根结点的权值为14,该值与未组成树的剩余结点的权 值相差不大，且不是其中的最大值。因此可以继续从未组成树的剩余结点中 选出权值最小的结点与二叉树合并，形成新的二叉树，如下图。此时新二叉树的根结点的权值为23,该值比剩余结点的权值大，且相差 较大。因此二叉树不能继续组合，否那么将不满足赫夫曼树的定义。将剩余结点组合成新的二叉树，如下图。将图所示的两颗二叉树合并，生成最
9、终的二叉树，此二叉树即为赫夫曼 树。如下图。二叉排序树.二叉排序树的定义二叉排序树(Binary Sort Tree)又称为二叉搜索树(Binary Search Tree), 其具体定义如下。(1)假设左子树不为空，那么左子树上的所有结点的值小于根结点的值。(2)假设右子树不为空，那么右子树上的所有结点的值大于根结点的值。(3)左、右子树本身也是一棵二叉排序树。由此定义可知，二叉排序树的左子树结点值根结点值(右子树结点值。 如果对二叉排序树进行中序遍历，可以得到一个递增的有序序列。如下图, 该二叉排序树中序遍历的顺序为1-2-3-4-5-6 o.二叉排序树插入结点二叉排序树插入结点时，如果原
10、二叉排序树为空，那么直接插入该结点； 如果该结点的值小于根结点的值，那么将该结点插入左子树；如果该结点的值 大于根结点的值，那么将该结点插入右子树。1 .二叉排序树删除结点叉排序树删除结点时有以下3种情况。(1)如果被删除的结点是叶结点，那么直接删除，不会影响二叉树原有的 规那么。(2)如果被删除的结点只有左子树或右子树，那么将该结点的子树作为 其双亲结点的子树，代替该结点；(3)如果被删除的结点有左右子树，那么可以根据中序遍历的结果，使用 被删除结点的直接前驱或后继替换该结点。4 .二叉排序树查找在最坏的情况下，二叉排序树查找需要的时间取决于树的深度。假设某 二叉排序树的结点个数为n,具体的
11、查找分析如下。(1)当二叉排序树接近于满二叉树时，其深度为log2n,因此在最坏 的情况下查找的时间复杂度为O(log2n)o(2)当二叉树形成单枝树时，其深度为n,在最坏的情况下查找的时间 复杂度为0(n)。如下图。平衡二叉树L平衡二叉树的定义由二叉排序树的查找分析可知，二叉排序树的查找效率与其形态有关。 二叉排序树的形态最好是均匀的，这样就产生了平衡二叉树(Balanced Binary Search)。平衡二叉树可以是空树，当其不为空树时，具有以下性质。(1)左右子树的深度差的绝对值不超过1。(2)左右子树也分别是平衡二叉树。平衡二叉树中的左子树深度减去右子树深度的值称为平衡因子BF (
12、BalanceFactor) o因此，平衡二叉树上所有结点的平衡因子只能是-1、0、 lo如果存在一个结点的平衡因子的绝对值大于1,那么该二叉树就不是平衡 二叉树，如下图。2 .构造平衡二叉树俄罗斯数学家格奥尔基(Georgii M.Adelson-Velskii)和叶夫根尼(EvgeniiM.landis）提出了一种动态保持平衡二叉树的方法。其基本思想是：在构造 平衡二叉树时，每当插入一个结点时，先检查是否因插入结点而破坏树的平 衡性，如果是，那么找出其中最小不平衡子树，调整最小不平衡树中各结点的 关系（在遵守二叉排序树规那么的前提下），以到达新的平衡。 B树LB树的定义B树（B-tree）
13、与平衡二叉树类似，不同的是，B树是一种平衡的多路查 找树（结点的孩子至少有两个，且每个结点可以存储多个数据元素）。数据库中的索引（索引存在于索引文件中，保存在磁盘中，帮助数据库 高效获取数据）通常会使用该树形结构。当数据库索引非常大（数据量越大, 索引文件越大），到达几个GB时，无法一次性加载到内存，而是逐一加载 每一个磁盘页（对应树的结点）。然而磁盘读写的速度相对于内存来说是很 慢的，为了减少二者吞吐量相差太多造成的系统消耗，比拟好的方法是减少 磁盘读写的次数。当使用树形结构作为索引时，每一个结点对应一个磁盘页，减少磁盘读 写次数就是缩减树的高度。因此，B树“矮胖”的特征，使其更适合作为数
14、据库的索引，其结点最大的孩子数量称为B树的阶，其大小取决于磁盘页的 大小。2.B树插入结点的实现定义一棵5阶的B树（平衡5路查找），需要插入的结点数据为3、8、 31、11、23、29、50、28o当前需要组成一棵5路查找树，那么M=5,分支结 点关键字的个数必须满足W4。具体实现过程如下。（1）先存入数据3、8、3k 11,变化过程如下图。（省略结点中表 示关键字个数的表示n与指针Ai o ）31 B+树与B*树1.B+树B+树是B树的升级版，一棵完整的B+树具有以下特点。（1）有k个子树的分支结点包含有k个元素，每个元素不保存数据， 只用来作索引，所有数据都保存在叶结点。（2）叶结点在B+
15、树的最底层（所有叶结点都在同一层），叶结点中存 放索引值、指向记录的指针、指向下一个叶结点的指针。叶结点按照关键字 的大小，从小到大顺序链接。（3）所有分支结点的元素都同时存在于子结点中，并且在子结点中是 最大或最小的元素。创立一棵完整的B+树，如下图。（为了更加清晰地展示B+树的结点, 图中分支结点忽略指针局部，特此说明。）2B*树B*树是B+树的变体，B*树不同于B+树的是：其非根和非叶结点上增加 了指向兄弟结点的指针。因此，对于一个M阶的B*树来说，非叶结点的关 键字个数至少为（2/3）*M。对于B+树来说，当一个结点满时，将分配一个新的结点，并将原结点 中1/2的数据复制到新结点，最后
16、在双亲结点中增加新结点的指针。因此， B+树的分裂只影响原结点和双亲结点，而不会影响兄弟结点（不需要指向兄 弟的指针）。而对于B*树来说，当一个结点满时，如果它的下一个兄弟结点未满，那 么将一局部数据移到兄弟结点中，再在原结点中插入关键字，最后修改双亲 结点的兄弟结点的关键字（因为兄弟结点的关键字范围发生改变）。如果兄 弟结点已满，那么在原结点与兄弟结点之间增加新结点，并各复制1/3的数据 到新结点，最后在双亲结点中增加新结点的指针。 红黑树红黑树（Red Black Tree）是一种自平衡二叉查找树，又可以称为平衡二 叉B树（Symmetric binary B-tree） o因此，红黑树和
17、平衡二叉树类似，都是 在进行插入和删除操作时通过特定的操作保持二叉排序树的平衡，从而获得 较高的查找性能。红黑树的每个结点上都有存储位来表示结点的颜色，即红 或者黑。一棵完整的红黑树满足以下4条规那么。（1）每个结点或者是黑色，或者是红色。（2）每个叶结点都是黑色（叶结点都为NIL或NULL）,根结点是黑 色。（3）如果一个结点是红色的，那么它的子结点必须是黑色的。（4）任意一个结点到其叶结点的路径都包含数量相同的黑结点。根据上述最后一个规那么可以推导出：如果一个结点存在黑子结点，那么 该结点肯定有两个子结点。第三课时上机练习（总结、练习题）L总结本章内容。2.通过题库发送相关测试题，检查学生
18、掌握情况。上机练习主要针对本章中需要重点掌握的知识点，以及在程序中容易出 错的内容进行练习，通过上机练习可以考察同学对知识点的掌握情况，对代码的熟练程度。第四课时 上机练习（总结、练习题） L总结本章内容2.通过题库发送相关测试题，检查学生掌握情况。上机练习主要针对本章中需要重点掌握的知识点，以及在程序中容易出 错的内容进行练习，通过上机练习可以考察同学对知识点的掌握情况，对代 码的熟练程度。习题教材第4章习题教 学 后 记课程名称第4章树计划 学时4学时内容分析本章主要介绍树的基本概念、二叉树、二叉树的遍历实现、赫夫曼树、 特殊的树教学目标 与教学要求要求学生掌握树的基本概念、掌握二叉树的基
19、本概念、掌握二叉树的遍 历方式、熟练编写二叉树的操作代码、了解特殊树形结构的概念与设计原理教学重点二叉树、二叉树的遍历实现、赫夫曼树、特殊的树教学难点二叉树、二叉树的遍历实现、赫夫曼树、特殊的树教学方式课堂讲解及ppt演示教学过程第一课时(树的基本概念、二叉树、二叉树的遍历实现)0内容回顾1.回顾上节内容，引出本课时主题。上节已经介绍了栈与队列，前面的章节介绍的都是线性结构，其数据元 素之间采用的都是一对一的关系。本章将主要介绍数据结构中的一种非线性 结构一一树。树形结构在文件系统与数据库开发中应用十分普遍，可以用来 提高数据排序和检索的效率。二叉树作为树形结构的一种特殊形式，无论是 应用于开
20、发，还是作为基础学习的对象，都具有重要的研究意义。因此，本 章将围绕二叉树的性质以及具体操作进行深入讲解，最后介绍一些特殊树形 结构的概念以及设计原理。2.明确学习目标(1)能够掌握树的定义(2)能够掌握树的基本术语(3)能够掌握二叉树的概念(4)能够掌握满二叉树(5)能够掌握完全二叉树(6)能够掌握二叉树的性质(7)能够掌握二叉树的存储(8)能够掌握二叉树的遍历方式(9)能够掌握二叉树的定义(10)能够掌握二叉树的创立(11)能够掌握二叉树的遍历(12)能够掌握整体测试C知识讲解树的定义1. 2.1节介绍数据的逻辑结构时，已经对树形结构进行了简单的说明， 树形结构是一种非线性结构，其数据元素
21、之间存在一对多的关系。树(Tree)是N (N20)个结点的有限集合，它满足以下4个条件。(1)有且只有一个特定的被称为根(Root)的结点。(2)除了根结点，其余每个结点都有且只有一个直接前驱。(3)每个结点都可以有多个后继，没有后继的结点称为叶结点(树叶)。(4)除了根结点，其他结点可以分为m (m0)个互不相交的有限集合TlT2Tm,其中每一个集合又可以视为一棵树，称为根的子树(SubTree)。 树的基本术语1 .度数一个结点的子树(或后继结点)的个数称为该结点的度数。度数为0的结点称为叶结点或终端结点, 外的分支结点称为内部结点。 如下图。结点称为叶结点或终端结点, 外的分支结点称为
22、内部结点。 如下图。度数不为0的结点称为分支结点，除根结点以 一棵树的度数指的是该树中结点的最大度数。1/根结点I分支结点AALcB;该结点为分支结点该结点的度数为3 ： 该结点为分支结点，该蜃金曲土薮短 !该结点为树叶、内部结点I 终端结点;(树叶)2 .结点关系结点的子树的根(结点的后继结点)称为该结点的孩子(Child),同时 该结点称为孩子结点的双亲结点(父结点)，具有同一双亲结点的孩子结点 互相称为兄弟结点。图中，结点B的孩子结点为结点D和结点E,换句话说，结点B是结点 D与结点E的双亲结点，结点B与结点C互为兄弟结点。3 .结点层次树也可以被视为一种层次结构，树中的每个结点都在固定
23、的层次上。结 点层次从根结点开始定义，根结点的层次为1,其孩子结点的层次为2,以 次类推。树中结点的最大层次称为树的深度(Depth)或高度。如下图。4 .有序树与无序树兄弟结点有顺序(不可交换)的树称为有序树，兄弟结点无顺序的树称 为无序树。 二叉树的概念二叉树是一种特殊的树形结构，其中的每一个结点最多只能有两个直接 后继。二叉树的递归定义如下。(1)有且只有一个根结点。(2)可以是空树，当为非空树时，它由一个根结点以及两棵互不相交且 分别称为左子树和右子树的二叉树组成。二叉树的任意结点最多只有两棵子树，也可以没有子树或者只有一棵子 树，因此二叉树的度数一定小于或等于2。二叉树严格区分左右子
24、树，即使 只有一棵子树也要区分左右。综上所述，二叉树具有以下5种基本形态。(1)空二叉树。(2)只有一个根结点。(3) 一个根结点和根结点的左子树构成。(4) 一个根结点和根结点的右子树构成。(5) 一个根结点和根结点的左右子树构成。 满二叉树满二叉树每层的结点数都是最大结点数，除了最后一层为叶结点，其余 所有结点都有左右子树。深度为k的满二叉树有2 k-1个结点，如下图。 完全二叉树对一棵具有n个结点的二叉树的结点按层序进行编号，如果编号为i （1 WiWn）的结点与同样深度的满二叉树的中编号为i （IWiWn）的结点位置 相同，1 .性质1二叉树的第i （il）1 .性质1二叉树的第i （
25、il）层中最多有2 i-1个结点。图所示的满二叉树 二叉树的性质中，第3层结点的个数为2 3-1=4个，第4层结点的个数为2 4-1二8个。2 .性质2深度为k的二叉树最多有2 kT个结点。在同等深度的二叉树中，满 二叉树的结点数最多，叶结点数最多。3 .性质3在任何一棵二叉树中，如果叶结点的数量为N,度数为2的结点数量为 N 2,那么N=N 2+1。假设该树中度数为1的结点数量为N 1 ,那么这棵树的总 结点数为N+N 1 +N 2 ,总结点数也可以是所有子结点数加1 （根结点）的 和，即 N 1 +2XN 2 +1。因此 N 1 +2XN 2 +1 =N+N 1 +N 2 ,得出 N二N
26、2 +1。二叉树的存储1 .二叉树的顺序存储使用顺序存储实现二叉树就是用一维数组存储二叉树中所有的结点，并 通过数组的下标表达结点在二叉树中的位置。图（a）中的完全二叉树在数组 中的存储形式如下图。2 .二叉树的链式存储在顺序存储不适用的情况下，可以考虑使用链式存储。使用链式存储表 示二叉树，其结点结构与双向循环链表一致，即一个数据域和两个指针域， 如下图。这样的链表称为二叉链表。Ichilddatarchild二叉树的遍历方式二叉树的遍历方式有很多，主要有以下4种。3 .先序遍历先序遍历就是先访问根结点，然后访问其左孩子，最后访问其右孩子， 其余子结点都遵循“根左右”的规那么。也就是说，对树
27、中的任意一个结点， 都是先访问该结点的数据，然后访问其左孩子，最后访问其右孩子。先序遍 历的访问顺序如下图。4 .中序遍历中序遍历就是先访问根结点的左孩子，然后访问根结点，最后访问根结 点的右孩子，其余子结点都遵循“左根右”的规那么。中序遍历的访问顺序如 图所示。5 .后序遍历后序遍历就是先访问左孩子，然后访问右孩子，最后访问根结点，其余 子结点都遵循“左右根”的规那么。后序遍历的访问顺序如下图。6 .层序遍历层序遍历与前3种方式不同，其访问从树的第一层开始，从上到下逐层 遍历，同一层中按照从左到右的顺序访问结点。层序遍历的访问顺序如图所 zTs o 二叉树的定义二叉树中的结点结构与链表类似，
28、代码如下所示。typedef int datatype;typedef struct node_tdatatype data;/*保存结点数据*/struct node_t *lchild, *rchild; /*指针，指向左右子树*/ btree_t; 二叉树的创立创立二叉树需要考虑该二叉树是完全二叉树还是非完全二叉树。1 .完全二叉树的创立如果对一棵有n个结点的完全二叉树的结点按层序进行编号，那么对任意 一个结点i (IWiWn)来说，有如下规律。(1)如果i=l,那么结点i无双亲，为根结点。(2)如果il,那么结点i的双亲结点是结点i/2。(3)如果2in,那么结点i的左孩子是结点2i,
29、否那么结点i为叶结点。(4)如果2i+ln,那么结点i的右孩子是结点2i+l,否那么结点i无右 孩子。根据上述规律，通过代码实现创立完全二叉树，例如代码参考教材4. 3. 2 节。2 .非完全二叉树的创立完全二叉树的规律不适用于非完全二叉树，通过代码实现创立非完全二 叉树，例如代码参考教材节。例同样使用了递归调用，与例4-1不同的是，程序允许用户选择是否创 建结点的左右孩子。如果输入符号#,那么当前创立不成立，直接返回NULL (即 结点指针指向为空)。输出结果如下所示。linuxubuntu:1000phone/data/chap4$ ./a.outq什什/*手动输入内容*/linuxubu
30、ntu:lOOOphone/data/chap4 $ 二叉树的遍历1.先序遍历先序遍历遵循“根左右”的规那么，其代码实现使用了递归调用的思想， 具体代码如下所示。/*先序遍历，参数为指向根结点的指针*/ int pre_order(btree_t *root)/*判断上一个结点是否有左(右)孩子*/if(root = NULL)return 0;)/*输出结点的数据*/printf (%d ，root-data);/*递归调用，如果有左孩子，输出左孩子的数据*/ if(root-lchild != NULL)pre_order(root-lchiId);)/*递归调用，如果有右孩子，输出右孩子
31、的数据*/ if (root-rchild != NULL)pre_order(root-rchiId);)return 0;)想，2.中序遍历中序遍历遵循“左根右”的规那么，其代码实现同样使用了递归调用的思 具体代码如下所示。/*中序遍历，参数为指向根结点的指针*/ int in_order(btree_t *root)/*判断上一个结点是否有左(右)孩子*/if(root = NULL)return 0;/*递归调用，如果有左孩子，输出左孩子的数据*/ if(root-lchild != NULL)in_order(root-lchild);/*输出结点的数据*/print f (H%ci ”，root-data);/大递归调用，如果有右孩子，输出右孩子的数据*/ if(root-rchild != NULL)in_order(root-rchild);return 0;)想，3.后序遍历后序遍历遵循“左右根”的规那么，其代码实现同样使用了递归调用的思 具体代码如下所示。