![4.1树课件-浙教版高中信息技术选修1_第1页](http://file4.renrendoc.com/view3/M00/3B/0D/wKhkFmaLOhOAf2bdAABzF3jwNrw806.jpg)
![4.1树课件-浙教版高中信息技术选修1_第2页](http://file4.renrendoc.com/view3/M00/3B/0D/wKhkFmaLOhOAf2bdAABzF3jwNrw8062.jpg)
![4.1树课件-浙教版高中信息技术选修1_第3页](http://file4.renrendoc.com/view3/M00/3B/0D/wKhkFmaLOhOAf2bdAABzF3jwNrw8063.jpg)
![4.1树课件-浙教版高中信息技术选修1_第4页](http://file4.renrendoc.com/view3/M00/3B/0D/wKhkFmaLOhOAf2bdAABzF3jwNrw8064.jpg)
![4.1树课件-浙教版高中信息技术选修1_第5页](http://file4.renrendoc.com/view3/M00/3B/0D/wKhkFmaLOhOAf2bdAABzF3jwNrw8065.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
4.1树情景导入PART1树的概念与特性一树的概念树是一种非线性的数据结构,用它能很好地描述有分支和层次特性的数据集合树在计算机领域中也有广泛应用,在编译系统中,用树表示源程序的语法结构。在数据库系统中,树形结构是数据库层次模型的基础,也是各种索引和目录的主要组织形式。一树的概念树是由n(n≧0)个节点构成的一个有限集合以及在该集合上定义的一种节点关系。节点:集合中的元素。空树:n=0的树。子树:树中某个节点下面的所有节点所构成的树。边:一颗具有n个节点的树有n-1条边。二基本术语·节点的度:树的一个节点所拥有的子树个数。·树的度:最大的节点的度。二基本术语·根节点:没有前驱的节点。·叶子节点:度为0的节点。·分支节点:度不为0的节点。·父节点或双亲节点:上端节点称为下端节点的父节点。·孩子节点:下端节点称为上端节点的孩子节点·兄弟节点:具有同一父节点的节点二基本术语·节点的层数:树中节点从根开始计算,根的层数为1,其他节点的层数等于父节点层数加1·树的高度或深度:树中节点的最大层数。根的层数为1。第1层第2层第3层第4层树的深度二基本术语·森林:0个或多个不相交的树的集合ABC练习【例1】(1)该树共有个
节点,
条边。(2)根节点的名称是
它有
个孩子节点,节点E.(选填:是/不是)根节点的孩子节点.(3)节点A和节点B的度分别是
,整棵树的度是
。(4)该树的分支节点的数量是
,叶子节点的数量是
。(5)节点C的层数是
,树的深度是
。(6)节点D的父节点是
,兄弟节点是
,孩子节点是
。109A3不是3、334623AB、CI、JPART2二叉树一二叉树的概念二叉树是一种特殊的树,是由n(n≧0)个节点构成的一个有限集合,且各个节点的度小于或等于2,二叉树的子树有左右之分,其次序不能任意颠倒(有序树)。ABCDEFGHABCDEFGH≠二二叉树的形态AABAC(1)空二叉树(2)只有根节点的单点树(3)只有根节点和左子树(4)只有根节点和右子树ABC(5)左右子树均非空三特殊二叉树1.完全二叉树设二叉树的深度为h,除第h层外,其它各层(1~h-1)的结点数都达到最大个数,第h层所有的结点都连续集中在最左边,这就是完全二叉树。ABCDEGHIFJ(1~h-1)层
第h层三特殊二叉树2.满二叉树每一层都是满的,每个节点的度要么是2,要么为0,而且所有叶子节点都在同一层。ABCDEGF练习【例2】观察如图所示的二叉树示意图,下列说法正确的是( )A.这是一棵完全二叉树B.这是一棵满二叉树C.这棵二叉树的深度是4D.这棵二叉树的度是4C四二叉树的性质1.二叉树的第i层上最多有
(i>=1)个节点。2.深度为h的二叉树最多有
(h>=1)个节点。3.在任意一棵二叉树中,若其叶子节点的数量为n0,度为2的节点数量为n2,则
。ABCDEGHIFJ
ABCDEGF四二叉树的性质4.具有n个结点的完全二叉树的深度
。5.给定n个节点,能构成
种不同的二叉树。ABCDEGHIFJABCDEGF
练习【举一反三1】已知二叉树T共有10个节点,其中度为1的节点数量为3,则叶子节点数量为()A.3B.4C.5D.6B练习【举一反三2】某棵树有5个节点,树的度和深度均为3,请画出这棵树所有可能的形态。练习【举一反三3】已知某二叉树总共有7个节点,其中叶子节点的个数为4,叶子节点的数据分别为1,2,3,4;每个双亲节点的数据值均为其孩子节点数据值之和。(1)该二叉树的深度为
。(2)该二叉树根节点的数据值为
。(3)若考虑叶子节点不同的排列情况,则该二叉树有
种画法。(4)请画出2棵符合条件的二叉树。31024练习一棵完全二叉树上有1001个节点,其中叶子节点的个数是(
)A.250B.500C.505D.501D练习一棵高度为4的完全二叉树上至少有(
)个节点A.15B.7C.8D.168PART3哈夫曼树一哈夫曼树4382路径:树中两个节点之间所经过的分支路径长度:一条路径上的分支数节点的权:给二叉树中的节点赋一个值节点带权路径长度:从根节点到一个节点的路径长度与该节点的权值的乘积树的带权路径长度:一棵树中所有叶子节点的带权路径长度之和WPL的公式:最优二叉树:在具有n个带权叶子节点的所有二叉树中,称带权路径长度WPL最小的二叉树为最优二叉树。在最优二叉树中权值较大的节点离根节点较近。
练习如图所示三棵树中哪棵树
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 注册会计师财务成本管理第十一章股利分配、股票分割与股票回购含解析
- 河南湿封市2025届高三地理第三次模拟考试试题含解析
- 2024版委托代理房屋买卖合同
- 2024年版物业管理权移交合同范本五件套
- 2024物品运输合同
- 2024版饲料购销合同
- 专业环卫保洁服务合同样本2024年适用
- GB/T 23850-2024工业高氯酸钠
- 2024年10月高教自考《急救护理学》试卷含解析
- 全国2022年春4月高等教育自考试急救护理学试题含解析
- 江西省孕产妇危重症救治及转运项目实施方案
- 过盈配合压装力计算
- 医院消防安全工作计划汇编3篇
- 广州市推进城镇污水处理提质增效工作经验分享
- 中职基础会计试题
- ZF变速箱故障代码表(中文)
- 非标机械设计计算大全
- 初一数学上册期中考试试卷及答案(人教版)
- 道路交通运输企业安全管理人员考试题库试题
- GB/T 31495.3-2015信息安全技术信息安全保障指标体系及评价方法第3部分:实施指南
- GB/T 30766-2014茶叶分类
评论
0/150
提交评论