热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

类属树(N数组树)

类属树(N-数组树)原文:https://www.geeksfo

类属树(N-数组树)

原文:https://www.geeksforgeeks.org/generic-treesn-array-trees/

泛型树是节点的集合,其中每个节点都是一个数据结构,由记录和其子节点的引用列表组成(不允许重复引用)。与链表不同,每个节点存储多个节点的地址。每个节点都存储其子节点的地址,第一个节点的地址将存储在一个名为 root 的独立指针中。

类属树是具有以下属性的 N 元树:

1.每个节点都有很多孩子。

2.每个节点的节点数事先未知。

例:

Generic tree

为了表示上面的树,我们必须考虑最坏的情况,即具有最多子节点的节点(在上面的例子中,6 个子节点),并为每个节点分配那么多指针。
基于该方法的节点表示可以写成:

C

//Node declaration
struct Node{
   int data;
   struct Node *firstchild;
   struct Node *secondchild;
   struct Node *thirdchild;
   struct Node *fourthchild;
   struct Node *fifthchild;
   struct Node *sixthchild;
}

上述表示的缺点是:


  1. 内存浪费–并非所有情况下都需要所有指针。因此,存在大量的内存浪费。

  2. 未知子节点数–每个节点的子节点数事先未知。

简单方法:

为了在节点中存储子节点的地址,我们可以使用数组或链表。但是我们会面临他们两个的一些问题。


  1. 链表中,我们不能随意访问任何孩子的地址。所以会很贵。

  2. 数组中,我们可以随机访问任意一个孩子的地址,但只能在其中存储固定数量的孩子地址。

更好的方法:

我们可以使用动态数组来存储孩子地址的地址。我们可以随机访问任何孩子的地址,向量的大小也不是固定的。

C

//Node declaration
struct Node{
    int data;
    vector children;
}

推荐阅读
  • 本文深入解析了JDK 8中HashMap的源代码,重点探讨了put方法的工作机制及其内部参数的设定原理。HashMap允许键和值为null,但键为null的情况只能出现一次,因为null键在内部通过索引0进行存储。文章详细分析了capacity(容量)、size(大小)、loadFactor(加载因子)以及红黑树转换阈值的设定原则,帮助读者更好地理解HashMap的高效实现和性能优化策略。 ... [详细]
  • 题目《BZOJ2654: Tree》的时间限制为30秒,内存限制为512MB。该问题通过结合二分查找和Kruskal算法,提供了一种高效的优化解决方案。具体而言,利用二分查找缩小解的范围,再通过Kruskal算法构建最小生成树,从而在复杂度上实现了显著的优化。此方法不仅提高了算法的效率,还确保了在大规模数据集上的稳定性能。 ... [详细]
  • 使用 ListView 浏览安卓系统中的回收站文件 ... [详细]
  • 本文介绍了几种常用的图像相似度对比方法,包括直方图方法、图像模板匹配、PSNR峰值信噪比、SSIM结构相似性和感知哈希算法。每种方法都有其优缺点,适用于不同的应用场景。 ... [详细]
  • 本文介绍如何使用线段树解决洛谷 P1531 我讨厌它问题,重点在于单点更新和区间查询最大值。 ... [详细]
  • 本文详细介绍了 PHP 中对象的生命周期、内存管理和魔术方法的使用,包括对象的自动销毁、析构函数的作用以及各种魔术方法的具体应用场景。 ... [详细]
  • 文章目录Golang定时器Timer和Tickertime.Timertime.NewTimer()实例time.AfterFunctime.Tickertime.NewTicke ... [详细]
  • 本文介绍了一种在ANSI C中动态分配二维数组的方法。通过创建指针数组并为每个指针分配连续空间,可以灵活地管理内存。文章还讨论了一些常见的错误和注意事项。 ... [详细]
  • 大类|电阻器_使用Requests、Etree、BeautifulSoup、Pandas和Path库进行数据抓取与处理 | 将指定区域内容保存为HTML和Excel格式
    大类|电阻器_使用Requests、Etree、BeautifulSoup、Pandas和Path库进行数据抓取与处理 | 将指定区域内容保存为HTML和Excel格式 ... [详细]
  • 在尝试对 QQmlPropertyMap 类进行测试驱动开发时,发现其派生类中无法正常调用槽函数或 Q_INVOKABLE 方法。这可能是由于 QQmlPropertyMap 的内部实现机制导致的,需要进一步研究以找到解决方案。 ... [详细]
  • 在《Cocos2d-x学习笔记:基础概念解析与内存管理机制深入探讨》中,详细介绍了Cocos2d-x的基础概念,并深入分析了其内存管理机制。特别是针对Boost库引入的智能指针管理方法进行了详细的讲解,例如在处理鱼的运动过程中,可以通过编写自定义函数来动态计算角度变化,利用CallFunc回调机制实现高效的游戏逻辑控制。此外,文章还探讨了如何通过智能指针优化资源管理和避免内存泄漏,为开发者提供了实用的编程技巧和最佳实践。 ... [详细]
  • 如何将TS文件转换为M3U8直播流:HLS与M3U8格式详解
    在视频传输领域,MP4虽然常见,但在直播场景中直接使用MP4格式存在诸多问题。例如,MP4文件的头部信息(如ftyp、moov)较大,导致初始加载时间较长,影响用户体验。相比之下,HLS(HTTP Live Streaming)协议及其M3U8格式更具优势。HLS通过将视频切分成多个小片段,并生成一个M3U8播放列表文件,实现低延迟和高稳定性。本文详细介绍了如何将TS文件转换为M3U8直播流,包括技术原理和具体操作步骤,帮助读者更好地理解和应用这一技术。 ... [详细]
  • 深入解析C语言中结构体的内存对齐机制及其优化方法
    为了提高CPU访问效率,C语言中的结构体成员在内存中遵循特定的对齐规则。本文详细解析了这些对齐机制,并探讨了如何通过合理的布局和编译器选项来优化结构体的内存使用,从而提升程序性能。 ... [详细]
  • 深入解析Android 4.4中的Fence机制及其应用
    在Android 4.4中,Fence机制是处理缓冲区交换和同步问题的关键技术。该机制广泛应用于生产者-消费者模式中,确保了不同组件之间高效、安全的数据传输。通过深入解析Fence机制的工作原理和应用场景,本文探讨了其在系统性能优化和资源管理中的重要作用。 ... [详细]
  • 在机器学习领域,深入探讨了概率论与数理统计的基础知识,特别是这些理论在数据挖掘中的应用。文章重点分析了偏差(Bias)与方差(Variance)之间的平衡问题,强调了方差反映了不同训练模型之间的差异,例如在K折交叉验证中,不同模型之间的性能差异显著。此外,还讨论了如何通过优化模型选择和参数调整来有效控制这一平衡,以提高模型的泛化能力。 ... [详细]
author-avatar
重报礼坊官肀网
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有