位置: IT常识 - 正文

树结构(树结构ADT知识点思维导图)

编辑:rootadmin
树结构 1.1 树的定义 树(Tree):个节点构成的有限集合。当n = 0时,称为空树。对于任一棵非空树(n>0),它具备以下性质: 树中有一个称为"根(Root)"的特殊节点,用r表示;其余节点可分为m(m>0)个互不相交的有限集、,...,,其中每个集合本身又是一棵树,称为原来树的子树(Sub ... 树结构1.1 树的定义

推荐整理分享树结构(树结构ADT知识点思维导图),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:树结构ADT知识点思维导图,树结构属于什么结构?,树结构的定义,树结构部首,树结构图,树结构图,树结构图,树结构属于什么结构?,内容如对您有帮助,希望把文章链接给更多的朋友!

树(Tree):个节点构成的有限集合。当n = 0时,称为空树。对于任一棵非空树(n>0),它具备以下性质:

树中有一个称为"根(Root)"的特殊节点,用r表示;其余节点可分为m(m>0)个互不相交的有限集、,...,,其中每个集合本身又是一棵树,称为原来树的子树(SubTree)。如下图:

1.2 树结构的术语

树结构中有很多概念术语,在深入讨论树结构之前,我们先来介绍下跟树结构有关的术语。为了方便理解记忆,结合具体的一棵树结构来进行介绍,树结构如下:

节点:树中存储的项。上图中的A-L都是节点。

根节点:树中最顶端的节点。在树结构中只有它没有父节点。上图中的A为根节点。

节点的度:一个节点含有的子树的个数。根节点A的度为3;子节点C的度为1。

树的度:树中最大节点度。树中最大节点度为3(根节点A和子节点B的度均为3),所以树的度为3。

子节点(孩子节点):紧邻一个给定的节点之下,并且直接与给定节点相连的一个节点。一个节点可以有多个子节点。上图中B-L都是子节点。

父节点(双亲节点):紧邻一个给定节点之上,且直接与给定节点相连的一个节点。一个节点只能有一个父节点。上图中A、B、C、D、H都是父节点。

兄弟节点:拥有共同父节点的子节点。上图中B、C、D是兄弟节点,E、F、G也是兄弟节点。

叶子节点:没有子节点的节点。或者说度为0的节点。上图中标绿的几个节点都是叶子节点。

内部节点:至少有一个子节点的节点。B、C、D、H都是内部节点。

边/分支:将一个父节点连接到其子节点的线。上图中的线就是边也称为分支。

后代(子孙):以某节点为根的子树中任一节点都称为该节点的后代。E、F、G是节点B的后代;H、K、L是节点C的后代,B-L的所有节点都是根节点A的后代。

树结构(树结构ADT知识点思维导图)

祖先:从根到该节点所经分支上的所有节点。节点D是I、J的祖先;根节点A是所有节点的祖先。

路径:连接一个节点与其后代节点边的序列。A-B-E和A-C-H-K都可以称作一条路径。

路径长度:路径中边的数目。路径A-B-E的路径长度为2;路径A-C-H-K的路径长度为3。

节点的层次:从根节点定义,根节点为第1层,根节点的子节点为第2层,依次类推。节点的层在上图中已经标出。

深度(高度):叶子节点所在的最大层次。上图中树的深度为4。

森林:m棵不相交的树的集合。分别以B、C、D为根节点的子树组成的集合可以看做一个森林。

以上就是树结构的一些术语。

1.3 树的分类

树结构可以分为两大类:有序树和无序树。树中任意节点间没有顺序关系,那么称其为无序树,也称自由树。相对的,树中的任意节点有顺序关系,称其为有序树。在有序树中,子节点被视为按照从左到右的顺序排列,最左边的子节点称为第一个子节点,最右边的子节点称为最后一个子节点。我们研究的最多的树结构就是有序树。而有序树中最具代表性的树结构就是二叉树。

二叉树就是度不超过2的有序树结构。 二叉树中的每个节点最多只能有两个分支,分别称为左子树和右子树。

根据二叉树的定义,会有如下两种极端的二叉树:

根据二叉树的形状,有以下几种常见的二叉树:

平衡二叉树:当且仅当任意节点的两棵子树的高度差不大于1的二叉树。

完全二叉树:除了最后一层外,其他层的节点数目都达到最大的二叉树。完全二叉树是平衡二叉树的一个特例,完全二叉树最后一层上的节点都是从左到右填充的。对于一颗k层的完全二叉树,其节点总数最少的情况是:最后一层只有一个节点,此时节点数目为:;其节点总数最多的情况是:最后一层节点数目达到最大,即满二叉树,此时节点数目为:。对于节点数目为k的完全二叉树,其深度为:

满二叉树:所有层的节点数目均达到最大的二叉树。满二叉树是完全二叉树的一个特例。对于深度为k的满二叉树,其节点数目是:;对于节点数目为k的满二叉树,其深度为:。

几种二叉树的结构图如下:

关于二叉树还有一个性质:二叉树中叶子节点数为(因为叶子节点的度为0,所以下标为0),度为2的节点数为 ,那么有: n0 = n2 + 1

解析:关于上面等式关系的求解我们可以这样考虑。假设二叉树的总节点数为,因为二叉树的节点度只有0、1、2三种情况,假设节点度为0、1、2的节点数分别为:n0、n1和n2。那么有n = n0 + n1 + n2。二叉树中节点度为1的节点有1条边连接到其子节点、节点度为2的节点有2条边连接到其子节点,假设二叉树有E条边,那么E = n1 + 2n2。而我们知道,在二叉树中节点总数和边的数目有这样的关系:n = E +1 = n1 + 2n2 + 1。联立加粗的两个等式,容易得出 n0 = n2 + 1。

本文链接地址:https://www.jiuchutong.com/zhishi/310958.html 转载请保留说明!

上一篇:织梦dedecms栏目添加自定义字段,增加栏目上传缩略图功能(织梦专题页模板)

下一篇:phpcms如何添加管理员(phpcms添加内容)

  • 未交增值税和应交增值税科目怎么调整
  • 原始凭证如何粘贴到记账凭证后面
  • 附加税计税依据文件
  • 年度财务报表怎么作废
  • 行政事业单位房产税免征文件
  • 成本类与费用类科目哪些区别
  • 应收账款无法收回分录
  • 签订设备维修合同会计分录
  • 金蝶软件怎么设置会计科目
  • 国家认定的高新技术企业是什么意思
  • 预付账款可以用应付账款借方
  • 跨年度的应收账款少记了怎么办
  • 包装物怎么入账
  • 租个人房屋办公怎么租
  • 少计提增值税0.01计入营业外
  • 去年的发票可以红冲重新开具吗?
  • 苹果设置输入法在哪里设置
  • 在银行买理财产品
  • 资产负债表中的预付款项目应根据什么填列
  • 联想笔记本bios密码忘记了怎么清除
  • 境内单位和个人将船舶出租到境外的,不征收车船税
  • 广告补贴申请报告
  • 票据权利消灭是啥意思
  • php 什么是类
  • 初学者如何
  • 苹果14数据线
  • 营改增后土地增值税
  • 进程com
  • 贷款减值损失准备怎么算
  • php foreach循环遍历数组
  • 本季度企业所得税
  • 生产企业的成本有哪些
  • php自定义变量的方法是
  • 分次预缴税额怎么算
  • 权益工具与金融负债的转换
  • thinkphp3.2框架
  • 计提下月工资怎么算
  • 基于骨骼关键点的动作识别
  • 销售费用期末余额
  • 流动资产处置利得
  • 快速上手:华硕路由器的wireguard服务器
  • python制作chm
  • wrap激活
  • 旅行社的增值税怎么算
  • 官方的问答
  • 挂靠到运输公司的车转让给个人如何交增值税
  • 职工福利费开支超过准予扣除标准的金额为1.2
  • 销售收入未及时入账
  • 预收账款和预付账款的区别
  • 确认委托代销手续费的会计分录
  • 存货成本主要包括
  • 公司员工报销没有发票挂内账有风险吗
  • 工人晚上加班的说说心情
  • 出口退税勾选后电子税务局查不到发票
  • 工会经费计提比例0.8%和2%有何区别
  • 计提风险准备金是什么意思
  • 注册表的命令
  • windows 批处理
  • win7电脑找不到无线网络连接图标
  • ubuntu14.04启动不了
  • mac如何修改
  • 右键无法新建wps
  • ubuntu20怎么连接蓝牙鼠标
  • win102020h2版本
  • Win10 Mobile RS2预览版14905更新内容大全:全新精致铃声
  • seg是什么文件
  • w10鼠标
  • linux如何修改gid
  • windows预览0x80072ee7
  • 麒麟系统怎么执行命令
  • json的parseobject
  • JQuery ZTree使用方法详解
  • pyinstaller如何用
  • JavaScript 和 Java 的区别浅析
  • scrollview用法
  • shell中setenv
  • android多指触控
  • android屏幕适配的五种方式
  • android简单项目及代码
  • 企业所得税优惠事项管理目录2023
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设