内蒙古大学《算法与数据结构》课件第4章树与二叉树
168页1、1第第4章章 树与二叉树树与二叉树4.1 树的定义和相关术语树的定义和相关术语4.2 二叉树二叉树4.3 树与森林树与森林4.4 森林与二叉树的关系森林与二叉树的关系4.5 Huffman树与编码树与编码2内蒙古大学内蒙古大学理工学院理工学院计算机学院计算机学院生命科学学院生命科学学院外国语学院外国语学院人文学院人文学院数数学学系系物物理理系系电电子子系系计计算算机机系系计计算算中中心心网网络络中中心心汉汉语语系系历历史史系系哲哲学学系系生生物物系系环环境境系系动动物物中中心心生生物物工工程程中中心心资资源源所所英英语语系系日日语语系系 行政机构行政机构树形结构是一种非线性结构,应用十分广泛。树形结构是一种非线性结构,应用十分广泛。如:行政机构、磁盘目录、家谱等如:行政机构、磁盘目录、家谱等3磁磁 盘盘 目目 录录4的定义和基本术语的定义和基本术语5例例5.1: Tree=(D, R)D=Book, C1, C2, C3, S1.1, S1.2, S2.1, S2.2, S2.3, S2.1.1, S2.1.2 R=, , , , , , , , , Book C1 C2 C3 S1.
2、1 S1.2 S2.1 S2.2 S2.3 S2.1.1 S2.1.2 ChapterSectionSectionv树是一种层次结构树是一种层次结构 (hierarchy structure)6v基本术语:基本术语:主要来源于家谱和树主要来源于家谱和树双亲、子女(双亲、子女(parent, child):):若若 R,则称,则称a是是b的双亲,的双亲,b是是a 的子女的子女(孩子孩子);结点度(结点度(degree):结点所拥有的子女数;结点所拥有的子女数;叶(叶(leaf):度为度为0的结点;的结点;分枝结点(分枝结点(branch node):度大于度大于0的结点;的结点;树的度树的度:树中最大的结点度;:树中最大的结点度;ABCDEFGHIJMKL7结点所在的层次(结点所在的层次(level):根在第根在第1层,其它任一结点所在的层是其双亲的层加层,其它任一结点所在的层是其双亲的层加1;深度或高(深度或高(depth):结点所在的层次的最大层数;结点所在的层次的最大层数;兄弟(兄弟(sibling):具有同一双亲的结点互称兄弟;具有同一双亲的结点互称兄弟;堂兄弟(堂兄弟(cous
3、in):双亲在同层的双亲在同层的非兄弟结点非兄弟结点互称堂兄弟;互称堂兄弟;423ABCDEFGHIJMKL18ABCACB无序有序祖先、子孙(祖先、子孙(ancestor):一个结点是它所有子树中的结点的祖先一个结点是它所有子树中的结点的祖先,这些结点是它的子孙这些结点是它的子孙;路径(路径(path):):是一结点序列是一结点序列n1,n2,n3,nk,并且前并且前1个结点是后个结点是后1个结个结点的双亲;它的长度是点的双亲;它的长度是k-1;有序树(有序树(ordered tree):):每个结点的子女由左到右是有次序的;否则是无序树;每个结点的子女由左到右是有次序的;否则是无序树;423ABCDEFG H IJMKL19ABCDEFGHIJKLM结点结点A、B、C的度分别为:的度分别为:3、2、1叶子:叶子:K,L,F,G,M,I,J结点结点A的孩子:的孩子:B,C,D结点结点B的孩子:的孩子:E,F结点结点I的双亲:的双亲:D结点结点L的双亲:的双亲:E结点结点B,C,D为兄弟为兄弟结点结点K,L为兄弟为兄弟树的度:树的度:3结点结点A的层次:的层次:0结点结点M的层次:的层
4、次:3树的深度:树的深度:3结点结点F,G为堂兄弟为堂兄弟结点结点A是结点是结点F,G的祖先的祖先10v森林(森林(Forest): m(m 0)棵互不相交的树的集合棵互不相交的树的集合.ArootBCDEFGHIJMKLF1112ABCDEFGHK根结点左子树左子树右子树右子树1314二叉树的二叉树的ADT定义定义 :ADT BinaryTree is Data 是有限个结点的集合是有限个结点的集合D。当。当D非空时,其中非空时,其中 有一根结点有一根结点t,其余结点被分为,其余结点被分为t的左子树和的左子树和 右子树。右子树。 Operations Constructor Process: 建立一棵空二叉树建立一棵空二叉树 Delete Process: 删除二叉树删除二叉树15 IsEmpty Process: 判断二叉树是否是空判断二叉树是否是空 Output: 若二叉树为空,则返回若二叉树为空,则返回true, 否则返回否则返回false Size Process: 计算二叉树的结点数计算二叉树的结点数size Output: size Height Process: 计算二
5、叉树的高度计算二叉树的高度height Output: height Root Process: 取二叉树根结点值取二叉树根结点值x Output: 根结点值根结点值x16Parent Input: node是二叉树中的一个结点是二叉树中的一个结点 Process: 求求node的双亲的双亲p,若,若node 是根,则是根,则p为空为空 Output: p CreateBinaryTree Input: 二叉树的某种形式的定义二叉树的某种形式的定义definition Process: 根据此定义根据此定义definition构造二叉树构造二叉树 MakeTree Input: data是根结点值,是根结点值,left是左子树,是左子树,right是右子树是右子树 Process: 创建二叉树,创建二叉树,data是根结点值,是根结点值,left是其左子树,是其左子树, right是其右子树是其右子树17 BreakTree Process: 拆分二叉树,拆分二叉树,data是根结点数据,是根结点数据,left是左子树,是左子树, right是右子树是右子树 Output: data,
《内蒙古大学《算法与数据结构》课件第4章树与二叉树》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》课件第4章树与二叉树》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页