位置: 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添加内容)

  • 华为手机屏幕使用时间在哪看(华为手机屏幕使用时长怎么看)

    华为手机屏幕使用时间在哪看(华为手机屏幕使用时长怎么看)

  • 红米k30和小米10的区别(红米k30和小米10pro哪个好)

    红米k30和小米10的区别(红米k30和小米10pro哪个好)

  • 支付宝在哪看访客记录呢(支付宝如何看访客)

    支付宝在哪看访客记录呢(支付宝如何看访客)

  • 苹果7无服务怎么解决感汉号(苹果7无服务怎么回事)

    苹果7无服务怎么解决感汉号(苹果7无服务怎么回事)

  • 为什么附近的人搜不到我的微信(为什么附近的人一直在线)

    为什么附近的人搜不到我的微信(为什么附近的人一直在线)

  • b站粉丝牌子怎么升级快(b站粉丝牌怎么来)

    b站粉丝牌子怎么升级快(b站粉丝牌怎么来)

  • 一加8pro防水级别(一加8pro的防水等级)

    一加8pro防水级别(一加8pro的防水等级)

  • 美团预订单是什么意思(美团预订单什么时候调度骑手)

    美团预订单是什么意思(美团预订单什么时候调度骑手)

  • 安卓手机可以装苹果系统吗(安卓手机可以装谷歌浏览器吗)

    安卓手机可以装苹果系统吗(安卓手机可以装谷歌浏览器吗)

  • 小米误删照片未同步能恢复吗(小米误删了照片怎么办)

    小米误删照片未同步能恢复吗(小米误删了照片怎么办)

  • word间距是什么意思(word字间距在哪里)

    word间距是什么意思(word字间距在哪里)

  • 微信公众号可以改几个字(微信公众号可以分组管理吗)

    微信公众号可以改几个字(微信公众号可以分组管理吗)

  • 华为手环4pro上市时间(华为手环4pro上市)

    华为手环4pro上市时间(华为手环4pro上市)

  • 电子计算器上ac键是什么键(电子计算器上AC)

    电子计算器上ac键是什么键(电子计算器上AC)

  • 魅族私密空间怎么进(魅族私密空间在哪里打开)

    魅族私密空间怎么进(魅族私密空间在哪里打开)

  • 红米note8怎么开通mipay(红米NOTE8怎么开内存扩展)

    红米note8怎么开通mipay(红米NOTE8怎么开内存扩展)

  • 高德地图能横屏吗(高德地图能横屏导航吗)

    高德地图能横屏吗(高德地图能横屏导航吗)

  • 淘宝人生账单怎么看(淘宝人生账单怎么看不了了)

    淘宝人生账单怎么看(淘宝人生账单怎么看不了了)

  • 拼多多怎么改手机号码(拼多多怎么改手机号)

    拼多多怎么改手机号码(拼多多怎么改手机号)

  • 华为运动手环如何开机(华为运动手环如何开机关机)

    华为运动手环如何开机(华为运动手环如何开机关机)

  • 苹果8系统40g怎么清理(苹果手机系统8g)

    苹果8系统40g怎么清理(苹果手机系统8g)

  • 支付宝可以自动充话费吗(支付宝可以自动绑定银行卡吗)

    支付宝可以自动充话费吗(支付宝可以自动绑定银行卡吗)

  • 手机热点咨询怎么删除(手机热点咨询怎么删)

    手机热点咨询怎么删除(手机热点咨询怎么删)

  • spf13-vim – Vim编辑器终极发布

    spf13-vim – Vim编辑器终极发布

  • win7电脑中如果文件夹属性没有安全选项怎么办?(win7电脑怎么样)

    win7电脑中如果文件夹属性没有安全选项怎么办?(win7电脑怎么样)

  • JS函数的4种调用方式(js函数怎么调用)

    JS函数的4种调用方式(js函数怎么调用)

  • 经济补偿影响下份工作吗
  • 年度企业所得税做账会计分录
  • 往来差异一般原因有哪些
  • 资产负债表中未交税金负数表示什么
  • 小规模纳税人增值税起征点
  • 购土地契税怎么算
  • 买二手房没满2年多少税
  • 关联交易所得税规定
  • 接受捐赠的材料会计分录怎么写
  • 专票金额和实际报销金额不符
  • 外币折算准则规范的外币交易
  • 研发支出费用化支出包括哪些
  • 年底给职工发啥实物
  • 交易性金融资产入账价值怎么计算
  • 辅导期一般纳税人预缴增值税
  • 企业所得税汇算清缴申报表
  • 小微企业免税销售额怎么算
  • 金融企业的代理贷款什么意思
  • 实验耗材发票内容怎么写
  • 商家收白条
  • 如何关闭win10自带杀毒软件
  • 什么叫交易类型
  • 小商业企业应交所得税
  • 上月材料入库会计分录
  • 小型微利企业怎么认定最新标准
  • 购买现金支票的工本费计入什么科目
  • 网件R6400路由器怎么样?R6400拆解与内部结构评测
  • 关于工程材料的图书有哪些
  • 没有抵扣的增值税怎么做账
  • linux sl
  • 惠普2600打印机故障排除
  • PHP:apache_child_terminate()的用法_Apache函数
  • 伦索伊斯马拉赫塞斯国家公园
  • 解决安装后软件icon一圈白边问题
  • php中哪个命令用来删除当前目录
  • 减免增值税会计处理
  • 自产产品用于应税项目为什么不考虑偷税
  • 利润表利息费用怎么填
  • vue清空form数据再重新赋值
  • bert模型能做什么
  • 无形资产摊销的方法
  • 什么是承兑汇票套现
  • 收到项目资本金入什么科目
  • 购买研发设备的发票可以申报创新券吗?
  • 其他货币资金期末有余额吗
  • 购买空调报销单怎么填
  • 代销手续费怎么做账
  • 收到销货方的返款分录
  • 抵押贷款的评估费会计分录
  • 收到加盟费应该怎么做账
  • 建筑行业会计怎么样,有前景吗
  • 三栏式明细账适用于总分类账
  • 印花税的征税对象有哪些
  • t3用友年底结束怎么建下一年
  • 企业预交所得税税率
  • 外地预缴需要缴纳印花税吗
  • 商品流通的企业
  • mysql数据库随机取数据
  • MySQL5.6.31 winx64.zip 安装配置教程详解
  • win8自带软件
  • windows2003企业版sp2密钥
  • windows7怎么打开开机启动项
  • mac睡眠后黑屏
  • windows远程桌面怎么开启
  • linux命令grep -rl
  • win8.1系统要求配置
  • 深入理解新发展理念,推进供给侧结构性改革 心得体会
  • win10复制c盘到新硬盘
  • input lead
  • Android Http请求方法汇总
  • linux中的shell命令
  • jquery控制台输出
  • 孙其功陪你学之——unity3d进程暂停
  • jquery实现下拉菜单
  • listview添加按钮
  • python魔法方法详解
  • ruby元编程第二版
  • 自然人扣缴端重置密码操作流程
  • 应纳税所得额怎么求公式
  • 资源税是地方税吗
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设