草庐IT

二叉树的性质和存储结构

zh-Note 2023-03-28 原文

2. 两种特殊的二叉树

  • 满二叉树

    • 定义：一棵深度为 k 且有 2^k - 1 个结点的二叉树称为满二叉树。

    • 特点：

      1. 每一层上的结点数都是最大结点数（即每层都满）；
      2. 叶子结点全部在最底层；

    • 对满二叉树结点位置进行编号

      • 编号规则：从根结点开始，自上而下，自左而西；
      • 每一结点位置都有元素；

  • 完全二叉树

    • 定义：深度为 k 的具有 n 个结点的二叉树，当且仅当其每一个结点都与深度同为 k 的满二叉树中编号为 1 ~ n 的结点一一对应时，称之为完全二叉树。

    • 注：在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树，一定是连续的去掉！！！
    • 特点：
      1. 叶子只可能分布在层次最大的两层上。
      2. 对任一结点，如果其右子树的最大层次为 i，则其左子树的最大层次为 i 或 i + 1。

3. 性质

  • 性质3：任意二叉数的叶子结点数 = 其度为2的结点数 + 1；

  • 性质4：具有 n 个结点的完全二叉树的深度为【 log2(n) 】+ 1。

    注：【 x 】：称作x的底，表示不大于x的最大整数。

    性质4表明了完全二叉树结点树n与完全二叉树深度k之间的关系。

  • 性质5：如果对一棵有n个结点的完全二叉树（深度为【 log2(n) 】+ 1）的结点按层序编号（从第1层，到第【 log2(n) 】+ 1层，没层从左到右），则对任一结点 (1<= i<= n)，有：

    1. 如果 i = 1，则结点 i 是二叉树的根，无双亲；如果 i > 1，则其双亲是结点【 i/2】。
    2. 如果 2i > n，则结点 i 为叶子结点，无左孩子；否则，其左孩子是结点 2i；
    3. 如果 2i + 1 > n，则结点 i 无右孩子；否则，其右孩子是结点 2i + 1。

4. 二叉树的顺序存储

  • 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。

    //二叉树顺序存储表示
#define MAXSIZE 100
Typedef TElemType SqBiTree[MAXSIZE] SqBiTree bt;

  • 缺点：

    最坏情况：深度为 k 的且只有 k 个结点的单支树需要长度为 2^k -1的一维数组。

  • 特点：结点间关系蕴含在其存储位置中浪费空间，适用于满二叉树和完全二叉树。

5.二叉树的链式存储结构

//二叉树链式存储表示
typedef struct BiNode{
    TElemType data;
    struct BiNOde *lchild,*rchild;//左右孩子指针
}BiNode,*BiTree;

  • 注：在 n 个结点的二叉链表中，有 n + 1 个空指针域。

  • 三叉链表

    typedef struct TriTNode{
   TElemType data;
    struct BiNode *lchild,*parent,*rchild;
}TriTNode,*TriTree;

二叉树二叉strongli3008601算法与数据结构

有关二叉树的性质和存储结构的更多相关文章

  1. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  4. ruby - Rack:如何将 URL 存储为变量？ - 2

    我正在编写一个简单的静态Rack应用程序。查看下面的config.ru代码:useRack::Static,:urls=>["/elements","/img","/pages","/users","/css","/js"],:root=>"archive"map'/'dorunProc.new{|env|[200,{'Content-Type'=>'text/html','Cache-Control'=>'public,max-age=6400'},File.open('archive/splash.html',File::RDONLY)]}endmap'/pages/search.

  5. ruby-on-rails - 一般建议和推荐的文件夹结构 - Sinatra - 2

    您将如何构建一个简单的Sinatra应用程序？我正在制作，我希望该应用具有以下功能:“应用程序”更像是一个包含所有信息的管理仪表板。然后另一个应用程序将通过REST访问信息。我还没有创建仪表板，只是从数据库中获取东西session和身份验证(尚未实现)您可以上传图片，其他应用可以显示这些图片我已经使用RSpec创建了一个测试文件通过Prawn生成报告目前的设置是这样的:app.rbtest_app.rb因为我实际上只有应用程序和测试文件。到目前为止，我已经将Datamapper用于ORM，将SQLite用于数据库。这是我的第一个Ruby/Sinatra项目，所以欢迎任何和所有建议-我应

  6. ruby-on-rails - 为什么在 Rails 5.1.1 中删除了 session 存储初始化程序 - 2

    我去了这个website查看Rails5.0.0和Rails5.1.1之间的区别为什么5.1.1不再包含:config/initializers/session_store.rb？谢谢 最佳答案 这是删除它的提交:Setupdefaultsessionstoreinternally,nolongerthroughanapplicationinitializer总而言之，新应用没有该初始化器，session存储默认设置为cookie存储。即与在该初始值设定项的生成版本中指定的值相同。 关于

  7. ruby-on-rails - 尝试设置 Amazon 的 S3 存储桶 : 403 Forbidden error & setting permissions - 2

    我正在关注Hartl的railstutorial.org并已到达11.4.4:Imageuploadinproduction.我做了什么:注册亚马逊网络服务在AmazonIdentityandAccessManagement中，我创建了一个用户。用户创建成功。在AmazonS3中，我创建了一个新存储桶。设置新存储桶的权限:权限:本教程指示“授予上一步创建的用户读写权限”。但是，在存储桶的“权限”下，未提及新用户名。我只能在每个人、经过身份验证的用户、日志传送、我和亚马逊似乎根据我的名字+数字创建的用户名之间进行选择。我已经通过选择经过身份验证的用户并选中了上传/删除和查看权限的框(而不

  8. ruby - 如何在 ruby​​ 中复制目录结构，不包括某些文件扩展名 - 2

    我想编写一个ruby​​脚本来递归复制目录结构，但排除某些文件类型。因此，给定以下目录结构:folder1folder2file1.txtfile2.txtfile3.csfile4.htmlfolder2folder3file4.dll我想复制这个结构，但不包含.txt和.cs文件。因此，生成的目录结构应如下所示:folder1folder2file4.htmlfolder2folder3file4.dll 最佳答案 您可以使用查找模块。这是一个代码片段:require"find"ignored_extensions=[".cs"

  9. ruby - 如何打印出 Mechanized 存储的 cookie？ - 2

    我正在使用mechanize登录网站，然后检索页面。我遇到了一些问题，我怀疑这是由于cookie中的某些值造成的。当Mechanize登录网站时，我假设它存储了cookie。如何通过Mechanize打印出存储在cookie中的所有数据？ 最佳答案 代理有一个cookie方法。agent=Mechanize.newpage=agent.get("http://www.google.com/")agent.cookiesagent.cookies.to_scookie返回一个Mechanize::Cookiesobject

  10. ruby-on-rails - 闪存消息存储在哪里？ - 2

    我以为它们存储在cookie中-但不，检查cookie没有任何结果。session也不存储它们。那么，我在哪里可以找到它们？我需要这个来直接设置它们(而不是通过flashhash)。 最佳答案 它们存储在inyoursessionstore.自rails2.0以来的默认设置是cookie存储，但请检查config/initializers/session_store.rb以检查您是否使用默认设置以外的东西。 关于ruby-on-rails-闪存消息存储在哪里？，我们在StackOverf

随机推荐