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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了php-如何在不使用广度优先遍历的情况下找到二叉树级别k的节点数？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1154字，纯文字阅读大概需要2分钟。

内容图文

给定这个二叉树(实际上,二叉树可以是随机的和动态的,这只是一个示例…)：

请参阅二叉树图像的链接：binary tree example

这是给定的事实：

>所有节点都连接到其父节点,以便我们可以从下到上(当然也从上到下)遍历.
>所有节点都包含有关其左右部分有多少个后代的信息.

问题是这样的：我需要找到一种方法来计算级别2中的节点总数(实际上,在任何级别上,但到目前为止,让我们专注于级别2).显然,如果我们事先知道二叉树的结构,但假设我们没有给定的事实,那么答案是3.

这里的另一个问题是我们将从第2级(我们的目标级别)而不是根节点开始.在此示例中,我选择了NODEF.

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

我正在寻找一种更实用的方法.但是,如果由于给定的数据不足而无法解决此问题,请让我知道应提供哪些其他数据以使其可解决.我将评估它是否可行.

我正在通过使用PHP和MySQL来创建网站.但是我只想要解决方案的概念或解释,更像是算法,而不是编程代码段或代码…

我希望有人能回答我…非常感谢！

解决方法:

“广度优先搜索”是实现此目的的方法.但是,如果您不想使用它,我建议在节点中包括指向兄弟的指针.如果您必须执行这种查询,通常可以节省很多钱.

编辑：

如果您可以对节点进行非规范化并将所有节点的级别和级别存储在表中,则可以毫无问题地进行查询.

SELECT * FROM nodes where level=2

内容总结

以上是互联网集市为您收集整理的php-如何在不使用广度优先遍历的情况下找到二叉树级别k的节点数？全部内容，希望文章能够帮你解决php-如何在不使用广度优先遍历的情况下找到二叉树级别k的节点数？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---