数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第六章 树
79页1、第六章 树,数据结构,第六章 树,第六章 树,知 识 点 二叉树及二叉树的存储结构 二叉树的遍历 树的基本概念 二叉排序树 哈夫曼树 难 点 二叉树遍历算法的设计 修改二叉树遍历算法,进行二叉树其它相关的操作,解决实际应用问题,要 求 熟练掌握以下内容: 理解树形结构的基本概念和术语 二叉树定义和存储结构 二叉树的遍历次序及二叉树遍历算法 了解以下内容: 树和二叉树之间的相互转换方法 线索二叉树的建立及遍历算法 树的应用:二叉排序树和哈夫曼树,第六章目录,6.1 树的定义和基本术语 6.2 二叉树 6.3 二叉树的遍历 6.4 树的应用 6.5 应用实例及分析 小 结 习题与练习,6.1.1 树的定义,树是n个结点的有限集合T,在一棵非空树中(n0)有且仅有一个称作根的结点;其余结点可分为m个(m0)互不相交的集合T1,T2Tm,其中,每一个集合本身又是一棵树,并称为根的子树。 当n=0时,称为空树。 有限集合T1,T2Tm应该“互不相交”,即任意两个集合不能有相重的结点。 树的各个结点有不同层次关系,这种关系通常用图形表示,但与自然界的树木相反,习惯上将整棵树的根画在最上层,如图5.
2、1所示。,图6.1 树的表示法,6.1.2 基本术语,1. 结点的度:树中每个结点具有的子树数或者后继结点数称为该结点的度(Degree)。度数为0的结点,即没有子树的结点叫作端结点或叶子结点。一棵树中各个结点度数的最大值叫做这个树的度。 2. 儿子结点和父亲结点:一个结点的子树的根或者后继结点称为该结点的儿子结点,反之,该结点则称为其后继结点的父亲结点。 3. 兄弟结点:同一个结点的儿子结点之间互称为兄弟结点。,4. 子孙结点和祖先结点:一个结点的子树中所有结点均称之为该结点的子孙结点。反之,从根结点到达一个结点的路径上的所有结点,都叫做该结点的祖先结点。 5. 树的深度:树是一种层次结构,树中结点的层次(Level)是从根结点算起的。根结点为第一层,其儿子结点为第二层。其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度或高度。 6. 森林:n个树的集合叫森林(Forest)。,树形结构的逻辑特征,树形结构的逻辑特征可用树中结点之间的父子关系来描述: 树中任一结点都可以有零个或多个直接后继结点(即儿子结点),但至多只能有一个直接前趋结点(即父亲结点)。 树中只有根
3、结点无前趋,它是开始结点; 叶结点无后继,它们是终端结点。 树形结构是非线性结构。,返回,6.2.1 二叉树的定义及其性质,一个二叉树是n个结点的有限集合(n0),此集合或者是空集(n=0),或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。 由上述定义可知,二叉树可以是空集,其根可以有空的左子树或右子树,或者左、右子树皆为空。 一般地,二叉树有五种基本形态,如图5.2所示。,图6.2 二叉树的基本形态,(a) 空二叉树 (b) 仅有一个根结点的二叉树 (c) 右子树为空的二叉树 (d)左子树为空的二叉树 (e)左、右子树均非空的二叉树,1. 满二叉树,在一个二叉树中,若第i层的结点数为2i-1,则称此层的结点数是满的,当树中的每一层都是满的,则称此二叉树为满二叉树。 即如果一个二叉树中,除最下一层的各结点度数为0以外,其它各层结点的度数均等于2,则此二叉树为满二叉树。 满二叉树的第一层有一个结点(即根结点),第二层有两个结点,依此类推。每一层的结点数都是上一层结点数的二倍。所以,在满二叉树的第i层共有2i-1个结点(i1),一个深度为h的满二叉树的结点总数为2h
4、-1。,图6.3 满二叉树,2. 完全二叉树,如果一个二叉树各层都是“满”的,只是最下面一层从右边起连续缺n个结点,这种二叉树叫做完全二叉树。 例如图5.3中的满二叉树,如果缺少从第11号至第15号结点(没有图中虚框里的几个结点),就是一个完全二叉树。 设完全二叉树的结点数为n,它与树的深度之间的关系为: 2h-1-1n 2h-1 即n值大于深度为h-1的满二叉树的结点数,但小于或等于深度为h的满二叉树的结点数。,对于完全二叉树,对其结点采用“按层编号”比较方便,即从根结点开始由上而下逐层给结点编号,同一层的结点由左向右编号。 对于完全二叉树中任一个编号为i的结点(1in),它的父结点和左、右儿子结点的编号与i值有如下的关系: 1) 如果i=1,则它是整个树的根结点,无父结点;若i1,则其父结点编号为 。 2) 如果2in,则其左儿子结点编号为2i;若2in,则无左儿子结点。 3) 如果(2i+1)n,则其右儿子结点编号为(2i+1);反之,则无右儿子结点。,6.2.2 二叉树的存储结构,1. 二叉树的顺序存储结构:用一个一维数组来存储二叉树的各个结点,显然,二叉树的结点必须按某种次序
《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第六章 树》由会员E****分享,可在线阅读,更多相关《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第六章 树》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页