c# - 从头开始实现树

Question

我正在尝试通过从头开始实现树来了解树。在这种情况下，我想用 C# Java 或 C++ 来做。（不使用内置方法）

所以每个节点都会存储一个字符，每个节点最多有 26 个节点。

我将使用什么数据结构来包含指向每个节点的指针？

基本上我正在尝试从头开始实现基数树。

谢谢，

score 3 · Accepted Answer

我将使用什么数据结构来包含指向每个节点的指针？

一个节点。每个节点都应该引用（最多）树中的 26 个其他节点。在 Node 中，您可以将它们存储在数组、LinkedList、ArrayList 或您能想到的任何其他集合中。

score 1 · Accepted Answer

这是我最近发现的一个对于树来说并不是一个糟糕的 API——虽然我需要图表，但它很容易看到它是如何设置来分离它所持有的数据的数据结构的，所以你可以拥有一个与 Iterator 等效的树在树中导航，依此类推。

score 1 · Accepted Answer

如果您实际上对速度比对空间更感兴趣，并且如果每个节点恰好代表一个字母（暗示您的最大值为 26），那么我只需使用一个简单的 26 个插槽数组，每个插槽都引用一个“节点”（节点是包含您的数组的对象）。

固定大小数组的好处是查找速度会更快。如果您正在查找已经保证是小写字母的 char "c"，则查找将非常简单：

nextNode=nodes[c-'a'];

字符串的递归查找将是微不足道的。

score 1 · Accepted Answer

您所描述的并不是一棵基数树……在基数树中，一个节点中可以有多个字符，并且子节点的数量没有上限。

您所描述的内容听起来更受字母表的限制...每个节点都可以是 az，并且后面可以跟另一个字母 az 等。区别对于您选择保存下一个节点指针的数据结构至关重要。

在你描述的树中，最容易使用的结构可能是一个简单的指针数组......你需要做的就是将字符（例如'A'）转换为其ascii值（'65'），然后减去开始偏移量（65）以确定您想要的“下一个节点”。占用更多空间，但插入和遍历速度非常快。

在真正的基数树中，您可能有 3、4、78 或 0 个子节点，并且您的“下一个节点”列表将具有排序、插入和删除的开销。慢得多。

我不会说 Java，但如果我在 C# 中实现自定义基数树，我会使用内置的 .NET 集合之一。编写自己的排序列表并不能真正帮助您学习树的概念，而且 .NET 集合的内置优化很难被击败。然后，您的代码很简单：查找下一个节点；如果存在，抓住它就走；如果没有，请将其添加到下一个节点集合中。

您使用哪个集合取决于您通过树实现的具体内容......每种类型的树都涉及插入时间、查找时间等之间的权衡。您所做的选择取决于对应用程序最重要的内容，而不是树.

有道理？

score 1 · Accepted Answer

感谢您的快速回复。

是的，snogfish 说的是正确的。基本上，它是一棵有 26 个节点 (AZ) + 一个 bool isTerminator 的树。

每个节点都有这些值，并且它们相互链接。

我还没有深入学习指针，所以我今天尝试使用 C# 中的不安全代码从头开始实现这一点，但徒劳无功。

因此，如果有人能为我提供使用内部树类开始使用 C# 的代码，我将不胜感激。一旦我可以开始使用它，我就可以将算法移植到其他语言，然后将其更改为使用指针。

非常感谢，迈克尔

score 0 · Accepted Answer

这并不重要。您可以使用链接列表、数组（但这将具有固定大小）或您语言的标准库中的 List 类型。

使用列表/数组将意味着做一些索引簿记来遍历树，所以最简单的方法可能是只保留对父项中子项的引用。

score 0 · Accepted Answer

看看这个 Simeon Pilgrim 博客，“代码营拼图回顾”。其中一个解决方案使用 C# 中的 Radix，您可以下载该解决方案。

7 回答 7