尝试自定义插入和删除功能
Trie with custom insert and delete functions
我需要在不改变其 O(n) 复杂度的情况下为 Trie 数据结构创建四个自定义函数：
- makeDir("pathToDir")
- 制作("pathToFile")
- 删除("pathToDir")
- 强制删除("pathToDirOrFile")
makeDir("pathToDir")：仅当它是有效路径时才将路径添加到 trie
make("pathToFile")：仅当路径是有效路径时才将路径添加到 trie（文件节点不能调用 makeDir() ）
delete("pathToDir")：仅当它没有子目录时才从 trie 中删除路径
forceDelete("pathToDirOrFile"): 删除路径及其子目录
例如，命令列表为：
makeDir("\dir");
makeDir("\dir\foo")
makeDir("\dir\foo\lol\ok"); /* incorrect path */
make("\dir\file");
makeDir("\dir\file\abc"); /* file can't have sub dirs */
delete("\dir"); /* has childs, incorrect */
delete("\dir\file");
forceDelete("\dir");
有没有人知道如何识别节点表示文件的路径？实现这些功能的最佳方式是什么？
正在验证和拆分路径
它是 OS 特定的，所以只需选择任何适用于您的目标系统路径的库。
特里树
一旦可以将路径拆分成多个部分，就可以构建一个 trie。将绳子放在边缘。例如，如果您有一条 foo/bar 路径，则将有 3 个节点和两条边：第一个 (1->2) 标记为 foo，第二个 (2->3) ) 标有 bar.
您可以在每个节点中存储一个标志以指示它是常规文件还是目录。
要检查目录是否为空，只要确保它的节点没有子节点即可。
要检查是否可以创建 directory/file，获取它的基本目录（路径的所有部分，除了最后一个），通过从根遍历你的 trie 来检查它是否存在，它的节点是目录，而不是常规文件。
高效遍历
您可以将边存储在将字符串映射到节点的散列 table 中。
我需要在不改变其 O(n) 复杂度的情况下为 Trie 数据结构创建四个自定义函数：
- makeDir("pathToDir")
- 制作("pathToFile")
- 删除("pathToDir")
- 强制删除("pathToDirOrFile")
makeDir("pathToDir")：仅当它是有效路径时才将路径添加到 trie
make("pathToFile")：仅当路径是有效路径时才将路径添加到 trie（文件节点不能调用 makeDir() ）
delete("pathToDir")：仅当它没有子目录时才从 trie 中删除路径
forceDelete("pathToDirOrFile"): 删除路径及其子目录
例如，命令列表为：
makeDir("\dir");
makeDir("\dir\foo")
makeDir("\dir\foo\lol\ok"); /* incorrect path */
make("\dir\file");
makeDir("\dir\file\abc"); /* file can't have sub dirs */
delete("\dir"); /* has childs, incorrect */
delete("\dir\file");
forceDelete("\dir");
有没有人知道如何识别节点表示文件的路径？实现这些功能的最佳方式是什么？
正在验证和拆分路径
它是 OS 特定的，所以只需选择任何适用于您的目标系统路径的库。
特里树
一旦可以将路径拆分成多个部分，就可以构建一个 trie。将绳子放在边缘。例如，如果您有一条 foo/bar 路径，则将有 3 个节点和两条边：第一个 (1->2) 标记为 foo，第二个 (2->3) ) 标有 bar.
您可以在每个节点中存储一个标志以指示它是常规文件还是目录。
要检查目录是否为空，只要确保它的节点没有子节点即可。
要检查是否可以创建 directory/file，获取它的基本目录（路径的所有部分，除了最后一个），通过从根遍历你的 trie 来检查它是否存在，它的节点是目录，而不是常规文件。
高效遍历
您可以将边存储在将字符串映射到节点的散列 table 中。