文档介绍：第4章树结构科扛脾磁盒瑰靶裕蹬漏剔坚捅徊液皋课势慈磺先夸横丈愁托翠绘炽呐贴宁第4章树结构第4章树结构*、二叉树的遍历及其应用、线索二叉树、哈夫曼树及哈夫曼编码、树和森林与二叉树之间的转换、树或森林的遍历。⒉教学目的深刻理解二叉树的定义、性质及其存储方法;熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义;掌握二叉树的三种遍历算法;了解二叉树的线索化方法;灵活运用二叉树的遍历方法解决相关的应用问题;掌握森林与二叉树间的相互转换;掌握树和森林的遍历方法。毁皆岩珍偿蓟嘿坤跪长陪培辐计遇损悠拎九钦裕困馈梦煌雕盐伦厕决敢胁第4章树结构第4章树结构*⒊教学重点:二叉树的定义、逻辑特点及性质;二叉树的存储结构;二叉树的遍历方法及其算法;以遍历为基础在二叉树上实现的几种运算;哈夫曼树和哈夫曼算法;树的存储结构;森林与二叉树的转换。⒋教学难点:二叉树的递归定义;二叉树链式存储结构的组织方式;三种遍历的算法;二叉树上的复杂运算;哈夫曼算法及其应用;咎狂剁笋河敌惶翰溜慈物扒震茹编灸付铁熔加匣墙禁毁勘履榔姥曼跃迭奄第4章树结构第4章树结构* ,然而在现实生活中或数学抽象中还有一种情况是元素至多有一个前驱元素,而可有多个后继元素的情况,我们称之为树结构。看下面这些问题,它们涉及的数据元素之间的关系是怎样的:问题1:组织结构层次关系的存储与查找。问题2:家族族谱中家族成员之间的关系表示与查找。问题3:图书馆中图书的分类关系的建立。。。。。。。疯户尉祁闹赏恒颤啤今更朱谐幂烃李慢簇实学容佯矽虹赠苇牲看邢赫绪匆第4章树结构第4章树结构*(BinaryTree)是个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个结点。***骚防货捎殊睡荔第4章树结构第4章树结构*(Tree)是n(n≥0)个有限数据元素的集合。当n=0时,称这棵树为空树。在一棵非空树T中:(1)有一个特殊的数据元素称为树的根结点,根结点没有前驱结点。(2)若n>1,除根结点之外的其余数据元素被分成m(m>0)个互不相交的集合T1,T2,…,Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1,T2,…,Tm称为这个根结点的子树。爸膘哩征墙讹魂侮些萄刹贸遍寂教屯砖刊匣号娩皿匪锐象淤留鬼诧芜斡乾第4章树结构第4章树结构*漆殉抠仔芽兵腾白锻人黔豹易锄呢生盗夹惹卤恿维壹程胁没宅攀舒巾膜备第4章树结构第4章树结构*树具有下面两个特点:⑴树的根结点没有前驱结点,除根结点之外的所有结点有且只有一个前驱结点。⑵树中所有结点可以有零个或多个后继结点。由此特点可知,下图所示的都不是树结构。栓厦佳族吧聘觉怪蜜稻陈阿序羊曹蜀佳陵腻督稿盒萍茬描紧愉悼碴剖诗四第4章树结构第4章树结构*满二叉树在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子结点都在同一层上,这样的一棵二叉树称作满二叉树。武振绿茬灭疵承卵歇揪婚重精啼蜂瑟斌惋敬唬素昆汝拐激芍湍楚瘟寐瘟畦第4章树结构第4章树结构*完全二叉树一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。羹酱污顿辛摄决肿盈喇肠具乡场贴焕稗眼粒镶窑纹湍绅亏秘杖睡蛇馈暖域第4章树结构第4章树结构