从头开始实现树

作者: 纾潆锦袖迷子
发布时间: 2024-09-18 11:29:42 (4天前)
转自：

8 条回复

0#
回复此人
℘ 宋唐 ℒº ѵ ℯ楚厦 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 这并不重要。您可以使用链接列表，数组（但这将具有固定大小），或使用您的语言的标准库中的列表类型。 </p> <P> 使用List /数组意味着要进行一些索引簿记来遍历树，因此最简单的方法是只使用对父项中子项的引用。 </p> </DIV>

编辑
1#
回复此人
ikun | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 这是我最近发现的一个不是一个糟糕的树API - 虽然我需要图表，看看如何设置它来分离它所持有的数据的数据结构是很方便的，所以你可以有一个等价于Iterator的树。浏览树，等等。 </p> <P> <a href="https://jsfcompounds.dev.java.net/treeutils/site/apidocs/com/truchsess/util/package-summary.html" rel="nofollow noreferrer"> https://jsfcompounds.dev.java.net/treeutils/site/apidocs/com/truchsess/util/package-summary.html </A> </p> </DIV>

编辑
2#
回复此人
枫 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 看看这个Simeon Pilgrim博客，“ <a href="http://simeonpilgrim.com/blog/index.php/category/code-camp/" rel="nofollow noreferrer"> Code Camp Puzzle评论 </A> “。其中一个解决方案在C＃中使用Radix，您可以下载解决方案。 </p> </DIV>

编辑
3#
回复此人
浮华丶 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 如果你实际上对速度比空间更感兴趣，并且如果每个节点只代表一个字母（隐含最多26个），那么我只使用一个简单的26个插槽阵列，每个插槽引用一个“节点”（节点是包含数组的对象）。 </p> <P> 固定大小的数组的好处是你的查找速度会快得多。如果你查找的char“c”已经保证是一个较低的套装字母，那么查找就像下面这样简单： </p> <pre> <code> nextNode=nodes[c-'a']; </code> </pre> <P> 对字符串的递归查找将是微不足道的。 </p> </DIV>

编辑
4#
回复此人
哦豁 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 感谢您的快速回复。 </p> <P> 是的，snogfish说是正确的。基本上，它的树有26个节点（A-Z）+一个bool是终结者。 </p> <P> 每个节点都有这些值，它们相互链接。 </p> <P> 我还没有深入学习指针，所以今天我尝试使用C＃中的不安全代码从头开始实现这一点。 </p> <P> 因此，如果有人能够使用内部树类为我提供开始使用C＃的代码，我将不胜感激。一旦我开始它，我可以将算法移植到其他语言，只需将其更改为使用指针。 </p> <P> 非常感谢，迈克尔 </p> </DIV>

编辑
5#
回复此人
坚挺的阿袁 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <BLOCKQUOTE> <BLOCKQUOTE> <P> 我将使用什么数据结构来包含指向每个节点的指针？ </p> </BLOCKQUOTE> </BLOCKQUOTE> <P> 一个节点。每个节点都应该引用树中的（最多）26个其他节点。在Node中，您可以将它们存储在数组，LinkedList，ArrayList或您可以想到的任何其他集合中。 </p> </DIV>

编辑
6#
回复此人
一生流水 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 你描述的不是 <EM> 相当 </EM> 基数树...在基数树中，节点中可以有多个字符，子节点数没有上限。 </p> <P> 您所描述的内容听起来更受限于字母...每个节点可以是a-z，后面可以跟另一个字母，a-z等。这种区别对于您选择保存下一个节点指针的数据结构至关重要。 </p> <P> 在您描述的树中，最简单的结构可能是一个简单的指针数组......您需要做的就是将字符（例如'A'）转换为其ascii值（'65'），然后减去起始值offset（65）确定你想要的“下一个节点”。占用更多空间，但插入和遍历非常快。 </p> <P> 在真正的基数树中，您可以有3个，4个，78个或0个子节点，并且“下一个节点”列表将具有排序，插入和删除的开销。慢得多。 </p> <P> 我不能说Java，但如果我在C＃中实现自定义基数树，我会使用其中一个内置的.NET集合。编写自己的排序列表并不能真正帮助您学习树概念，并且.NET集合的内置优化很难实现。然后，您的代码很简单：查找下一个节点;如果存在，抓住它去;如果没有，请将其添加到下一个节点集合中。 </p> <P> 您使用哪个集合取决于您通过树实现的具体内容......每种类型的树都需要在插入时间，查找时间等之间进行权衡。您所做的选择取决于对应用程序最重要的是什么，而不是树。 </p> <P> 合理？ </p> </DIV>

编辑

登录后才能参与评论