草庐IT

php - 如何在不使用广度优先遍历的情况下找到二叉树第 k 层的节点数？

coder 2023-10-19 原文

给定这个二叉树(实际上，二叉树可以是随机的和动态的，这只是一个例子...):

请参阅二叉 TreeMap 像的链接:binary tree example

这是给定的事实:

  1. 所有节点都连接到它们的父节点，这样我们就可以从下到上遍历(当然也可以从上到下遍历)。
  2. 所有节点都保存关于它们的左右部分有多少个后代的信息。

问题是这样的:我需要找到一种方法来计算第 2 层中的节点总数(实际上，在任何层中，但现在，让我们专注于第 2 层)。显然，如果我们事先知道二叉树的结构，答案是 3，但假设我们没有这张图片，只有给定的事实。

这里的另一个问题是我们将从第 2 层(我们的目标层)中的节点开始，而不是根节点。在此示例中，我选择了节点 F。

我知道使用广度优先顺序遍历是直接的解决方案，但我发现它太耗时了，因为每次我读取一个节点时，我都会从数据库中查询它。

我正在寻找更实用的方法。但是如果由于给定数据不足而“不可能”解决这个问题，请告诉我应该提供哪些其他数据才能解决这个问题。我会评估它是否可行。

顺便说一句，我正在创建一个网站并使用 PHP 和 MySQL。但我只想要解决方案的概念或解释，更像是一种算法而不是编程片段或代码...

希望有人能回答我...非常感谢!

最佳答案

“广度优先搜索”是一种方法。但是，如果您不想使用它，我建议您在节点中包含指向兄弟的指针。如果您通常必须执行此类查询，那将是一个很大的节省。

编辑:

如果您可以对节点进行非规范化，并将所有节点的同级和级别存储在表中，那么您就可以毫无问题地进行查询。

SELECT * FROM nodes where level=2

关于php - 如何在不使用广度优先遍历的情况下找到二叉树第 k 层的节点数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7456354/

点数何在section给定有节phpmysqlalgorithmbinary-treetree-traversal

有关php - 如何在不使用广度优先遍历的情况下找到二叉树第 k 层的节点数？的更多相关文章

  1. ruby - 如何在 Ruby 中顺序创建 PI - 2

    出于纯粹的兴趣，我很好奇如何按顺序创建PI，而不是在过程结果之后生成数字，而是让数字在过程本身生成时显示。如果是这种情况，那么数字可以自行产生，我可以对以前看到的数字实现垃圾收集，从而创建一个无限系列。结果只是在Pi系列之后每秒生成一个数字。这是我通过互联网筛选的结果:这是流行的计算机友好算法，类机器算法:defarccot(x,unity)xpow=unity/xn=1sign=1sum=0loopdoterm=xpow/nbreakifterm==0sum+=sign*(xpow/n)xpow/=x*xn+=2sign=-signendsumenddefcalc_pi(digits

  2. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  3. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  4. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  5. ruby - 默认情况下使选项为 false - 2

    这是在Ruby中设置默认值的常用方法:classQuietByDefaultdefinitialize(opts={})@verbose=opts[:verbose]endend这是一个容易落入的陷阱:classVerboseNoMatterWhatdefinitialize(opts={})@verbose=opts[:verbose]||trueendend正确的做法是:classVerboseByDefaultdefinitialize(opts={})@verbose=opts.include?(:verbose)?opts[:verbose]:trueendend编写Verb

  6. ruby - 如何在续集中重新加载表模式？ - 2

    鉴于我有以下迁移:Sequel.migrationdoupdoalter_table:usersdoadd_column:is_admin,:default=>falseend#SequelrunsaDESCRIBEtablestatement,whenthemodelisloaded.#Atthispoint,itdoesnotknowthatusershaveais_adminflag.#Soitfails.@user=User.find(:email=>"admin@fancy-startup.example")@user.is_admin=true@user.save!ende

  7. ruby - 如何在 Ruby 中拆分参数字符串 Bash 样式？ - 2

    我正在为一个项目制作一个简单的shell，我希望像在Bash中一样解析参数字符串。foobar"helloworld"fooz应该变成:["foo","bar","helloworld","fooz"]等等。到目前为止，我一直在使用CSV::parse_line，将列分隔符设置为""和.compact输出。问题是我现在必须选择是要支持单引号还是双引号。CSV不支持超过一个分隔符。Python有一个名为shlex的模块:>>>shlex.split("Test'helloworld'foo")['Test','helloworld','foo']>>>shlex.split('Test"

  8. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

  9. ruby - 如何在 Lion 上安装 Xcode 4.6，需要用 RVM 升级 ruby - 2

    我实际上是在尝试使用RVM在我的OSX10.7.5上更新ruby，并在输入以下命令后:rvminstallruby我得到了以下回复:Searchingforbinaryrubies,thismighttakesometime.Checkingrequirementsforosx.Installingrequirementsforosx.Updatingsystem.......Errorrunning'requirements_osx_brew_update_systemruby-2.0.0-p247',pleaseread/Users/username/.rvm/log/138121

  10. ruby-on-rails - 如何在 ruby​​ 交互式 shell 中有多行？ - 2

    这可能是个愚蠢的问题。但是，我是一个新手......你怎么能在交互式ruby​​shell中有多行代码？好像你只能有一条长线。按回车键运行代码。无论如何我可以在不运行代码的情况下跳到下一行吗？再次抱歉，如果这是一个愚蠢的问题。谢谢。 最佳答案 这是一个例子:2.1.2:053>a=1=>12.1.2:054>b=2=>22.1.2:055>a+b=>32.1.2:056>ifa>b#Thecode‘if..."startsthedefinitionoftheconditionalstatement.2.1.2:057?>puts"f

随机推荐