从零开始实现树

Question

我想通过从头开始实现一棵树来了解树。 在这种情况下，我想用C＃Java或C++来完成。 （不使用内置的方法）

所以每个节点将存储字符和将有最大每个节点26个的节点。

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

基本上我试图从零开始实施基数树。

感谢，

Answer 1

你描述的不是很一个基数树......在基数树，你可以在一个节点的多个字符，并且对孩子节点的数量没有上限。

你所描述的声音由字母更多的限制是什么？每个节点可以是AZ，并且可以跟另一个字母，AZ等的区别是你选择持有您的下一个数据结构的关键 - 节点指针。

在你描述的树，用可能是指针的简单数组的最简单的结构......所有你需要做的是字符（如“A”）转换为字符的ASCII值（“65”），并减去起始偏移量（65）以确定你想要哪个'下一个节点'。占用更多的空间，但插入和遍历速度非常快。

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

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

您使用收集取决于你正在通过树实现什么......每一个类型的树包括插入时间，查询时间等你的选择取决于什么是最重要的应用程序之间进行权衡，而不是树。

有意义吗？

Answer 2

我会用什么数据结构包含指向每一个节点？

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

Answer 3

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

使用列表/阵列将意味着做一些指数簿记遍历树，所以它可能是最容易使用的只是不停地引用父的孩子们。

Answer 4

这是我最近发现的一个不错的树型API - 虽然我需要图表，但很容易看到它是如何设置的，以便为它所持有的数据分开数据结构，因此您可以使用树型结构相当于Iterator在树中导航，等等。

https://jsfcompounds.dev.java.net/treeutils/site/apidocs/com/truchsess/util/package-summary.html

Answer 5

如果你实际上更感兴趣的速度比空间，如果每个节点代表只有一个字母（由最高的26暗示的），那么我只用26个时隙，每个的简单数组引用一个“节点”（节点是包含你的数组的对象）。

的好处约一个固定大小的数组是你的样子起来会更快。如果你正在寻找了一个已经保证在较低的套管字母字符“C”，外观起来会是那么容易，因为：

nextNode=nodes[c-'a']; 

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

Answer 6

看看这个西麦朝圣者博客中，“Code Camp Puzzle Reviewed”。其中一种解决方案在C＃中使用Radix，您可以下载该解决方案。

Answer 7

感谢您的快速回复。

是snogfish说是正确的。 基本上，它的一个有26个节点（A-Z）+一个bool的树是Terminator。

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

我还没有深入地学习过指针，所以今天我试着从头开始使用C＃中不安全的代码来实现这一点，这是徒劳的。

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

非常感谢， 迈克尔