问题标签 [prefix-tree]

我正在开发一个 c++ 程序和我的团队，我无法弄清楚如何使用 inOrder 遍历生成前缀代码的逻辑。我们已经构建了 PrefixCode Tree，我们希望从中生成代码。

由于我们遇到了逻辑问题，我不知道是否需要提供任何代码。如果你需要任何让我知道。

谢谢。

我正在尝试创建一个将 C# 类对象序列化为 XML 的 POST 函数。

我遇到很大困难的部分是将命名空间前缀添加到子根元素的子元素，所以在这种情况下，contact只有子元素。

我似乎能够将前缀添加到子元素的唯一方法contact是通过SerializerNamespace类添加它们，但是我只能将它附加到根元素，CreateContact.

我怎样才能做到这一点？

当前生成的 XML：

序列化功能：

XML 类结构：

所需的 XML：

我的数组中有 NSStrings：

我想传递一个搜索字符串来查找所有需要的字符串。例如，如果我传递“ax”，那么它将返回 3 个字符串，如果我传递“axx”，那么它将返回 2 个字符串。

性能在这里也很关键。该方法应如下所示：

我通常使用NSPredicate，但这次我可能需要使用前缀树或二叉树，我不确定，但它应该更快。任何建议或实施链接。

我从 2 个不同的 XSD 中获得了 2 个类，其中一个是它的子节点，根类有一个子节点的属性（xmlelement 数组），我需要子节点有不同的前缀。这是我的代码：

然后我序列化根：

XML 文件是以正确的格式创建的，但是子根具有命名空间，我不需要它，只在根节点中。

我知道在 trie 中搜索给定前缀的时间为 O(M)，其中 M 是插入到 trie 中的任何单词的最大长度。

但是检索所有以特定前缀开头的元素的时间复杂度是多少？

我想到了一个可能的答案：

O(M+n) 其中 n 是以前缀开头的单词数。想法：搜索前缀在 O(M) 中。然后我有一个包含所有以给定前缀开头的单词的 subtrie，我只需要遍历它。问题（可能）：前缀树中的节点多于单词。但也许有某种形式的有效存储，这样我就不必看它们了？

我正在尝试解决此处描述的键盘自动完成问题。 问题是在给定一些字典和自动完成规则的情况下，计算一个单词需要多少次击键。例如，对于字典：

我们得到以下结果（请参阅上面的链接以获得进一步的解释）：

快速解释：如果用户键入h，则e自动完成，因为所有以开头的单词h也有e第二个字母。现在，如果用户输入l，另一个l被填充，给单词 2 笔画hell。当然，hello还需要再打一针。请参阅上面的链接以获取更多示例。

我的Trie代码如下，它工作正常（取自https://en.wikipedia.org/wiki/Trie）。Stack代码是从根解析树（见下面的编辑）：

我不知道如何计算笔画数：

这是从根解析树的代码：

任何想法或建设性意见都会有所帮助，谢谢！

编辑

@SergiyKolesnikov 的回答很好。为了避免调用endsWith(). 我刚刚在 Trie 类中添加了一个布尔字段：

在插入（）的末尾：

然后只需替换curr.value.endswith('$'):为curr.eow. 谢谢你们！

我正在存储城市列表（从文件中读取）及其相应的纬度和经度值。在每个城市的末尾，我试图附加经度和纬度值。

因此，例如，特里的弗里蒙特看起来像

F->R->E->M->O->N->T->(经纬度)

我能够成功地将值插入到 trie 中，但是当我尝试搜索特定城市时，经度和纬度值返回为 (null)

这是我的实现

我正在研究一个带有前缀的实现，我正在尝试构建以下内容

F->R->E->T->(纬度+经度)

我已经实现了插入功能，它似乎正在工作。我通过打印出相应的纬度和经度值来验证这一点。

我遇到的问题是在我的搜索功能中，纬度和经度值返回(null)。搜索功能也确实为单词返回 true。

目前我无法理解根本问题在哪里

插入函数

我的搜索功能

在我的插入函数中，是否正确添加了纬度和经度值？

编辑

我的结构的定义

我的哈希码只返回单词的整个标题。我想让它显示结果，只使用至少 2 个单词（以后）的关键字，然后显示结果（获取函数）。

我的哈希码

样本输出：

输入整个标题时

输入关键字时（即使输入关键字，我也需要显示结果）

我需要的是：输出：Cheater - Kygos 和他们名字中带有 chea 的其他词

我想实现一个 trie 来检查路径的有效性，所以我会通过按目录分解它来构建一个包含所有可能路径结构的树。所以类似的东西/guest/friendsList/search会从根节点到它的 child guest，然后是 guest 的 child friendsList，然后是 friendsList 的 child search。如果搜索是叶节点，那么我的字符串/guest/friendsList/search将被视为有效。

这是一个 trie 有用的东西吗？我见过的所有尝试的实现都处理每个节点上的单个字母，但它们可以是整个字符串吗？特定于这种实现的特里树以及我正在尝试做的只是一个基本树吗？

谢谢！