版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
树与二叉树
选修一：数据结构树树形逻辑结构的应用树的基本概念树是n（n≥0）个结点的有限集合，n=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：1）有且仅有一个特定的结点称为根的结点。2）当n
>1时，其余结点可分为m（m>0）个互不相交的有限集合T,T,…,T
，其中每个集合本身又是一棵树，并且称为根结点的子树。树的基本概念非空树的特点：🎄有且仅有一个根节点ꢀ🎄没有后继的结点称为“叶子结点”（或终端结点）🎄有后继的结点称为“分支结点”（或非终端结点）🎄除了根节点外，任何一个结点都有且仅有一个前驱🎄每个结点可以有0个或多个后继。树的基本概念下列是否为树形结构？否，除根节点外，任何一个节点都有且仅有一个前驱数的基本概念属性：n个结点的树，有n-1条边树的高度——总共多少层结点的度——有几个孩子树的度——各结点度的最大值二叉树二叉数的基本概念二叉树是n（n≥0）个结点的有限集合：①n=0时，二叉树是一棵空树。。②当n
≠0时，二叉树是由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。二叉数的特点①每个结点至多只有两棵子树。②左右子树不能颠倒（二叉树是有序树）二叉数的五种状态特殊的二叉树—满二叉树满二叉树：每一层的节点数都达到最大值特殊的二叉树--完全二叉树当且仅当其每个结点都与高度为h的满二叉树中的结点一一对应时，称为完全二叉树特点：①只有最后两层可能有叶子结点②最多只有一个度为1的结点特殊的二叉树不是完全二叉树完全二叉树如果某结点只有一个孩子，一定是左孩子该二叉树是完全二叉树吗？二叉数的常考性质
第
1
层：20第2层：21第
3
层：22第4层：23二叉数的常考性质③在任意一棵二叉树中，若度为2的节点数量为n2，
叶子节点数为n0，则n0＝n2＋1（叶子节点比分支节点多一个）
二叉数的存储结构——顺序存储t[0]t[1]t[2]……i结点的左右孩子怎么表示？二叉数的存储结构——顺序存储如果不是完全二叉树，依然按层序将各节点顺序存储，结点编号将无法反映出结点间的逻辑关系二叉数的存储结构——顺序存储二叉数的存储结构——顺序存储
二叉数的存储结构——链式存储对于非完全二叉树，怎样存储才能避免空间浪费呢？左指针右指针二叉数的遍历遍历：按照某种次序把所有结点都访问一遍先/中/后序遍历：基于树的递归特性确定的次序规则层次遍历：基于树的层次特性确定的次序规则二叉数的遍历二叉树的递归特性：①要么是个空二叉树②要么就是由“根节点+左子树+右子树”组成的二叉
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 药品集中招标合作协议样本
- 学校网络升级国防光缆施工合同
- 养殖行业培训租赁协议
- 退休工程师技术支持合同
- 机场航站楼幕墙安装协议
- 舞蹈室租赁合同
- 酒店屋顶防水维护服务合同
- 医疗卫生合作的经济合同管理办法
- 暂停职务留薪协议
- 博物馆展区铁艺栏杆施工合同
- 当代社会政策分析 课件 第九章 妇女社会政策
- 《基本政治制度》名师教案
- 2024年网格员考试题库1套
- 2024年共青团入团积极分子考试题库及答案
- 2024年职业技能“大数据考试”专业技术人员继续教育考试题库与答案
- 江苏高职单招报考指南
- 心脏介入手术配合
- 学生骑车安全承诺书
- 核电站寿命评估技术
- 2023-2024学年辽宁省大连市名校联盟八年级（上）联考生物试卷（含解析）
- 有色金属熔炼与铸锭课件
评论
0/150
提交评论