我可以使用在每个节点上都有一个完整单词的特里吗？ [英] Can I use a trie that has a whole word on each node?

问题描述

我想实现一个特里来检查路径的有效性，因此我将构建一棵树，通过按目录将其分解，其中包含所有可能的路径构造。因此，诸如 / guest / friendsList / search 之类的东西将从根节点转到其子 guest ，然后是访客的子 friendsList ，然后friendsList的孩子搜索。如果搜索是叶节点，则我的字符串 / guest / friendsList / search 将被视为有效。

I want to implement a trie to check for the validity of paths, so I would have a tree built that contains all the possible path constructions by breaking it down by directory. So something like /guest/friendsList/search would go from the root node to it's child guest, then guest's child friendsList, and then friendsList's child search. If search is a leaf node then my string /guest/friendsList/search would be considered valid.

这是吗尝试一些有用的东西。我见过的trys的所有实现都在每个节点上处理单个字母，但是可以代替整个字符串吗？特里树是否专门针对这种实现方式，而我想尝试做的只是一棵基本树？

Is this something a trie would be useful for. All the implementations of tries I've seen deal with individual letters at each node, but can they be whole strings instead? Is a trie specific to this kind of implementation and what I'm trying to do just a basic tree?

谢谢！

推荐答案

您绝对可以做到这一点，尽管我通常将其称为目录树而不是特里树，因为您实际上是在将文件系统建模为树结构而不是存储许多不同字符串的前缀。实际上，操作系统可能在磁盘上具有用于表示文件系统的类似数据结构！

You can absolutely do this, though I'd typically call this a directory tree rather than a trie since you're essentially modeling the file system as a tree structure rather than storing lots of prefixes of different strings. In fact, the OS probably has a similar data structure on disk for representing the file system!

这篇关于我可以使用在每个节点上都有一个完整单词的特里吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！