在C++11中,打印出一个类似JSON的trie结构的扁平化名称空间可以通过递归或迭代的方式来实现。下面是一个迭代的解决方案,它使用了栈来避免递归调用。
#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
struct TrieNode {
std::unordered_map<char, TrieNode*> children;
bool isEndOfWord;
std::string prefix;
TrieNode(const std::string& prefix = "") : isEndOfWord(false), prefix(prefix) {}
};
void printTrie扁平化名称空间(TrieNode* root) {
if (!root) return;
std::stack<std::pair<TrieNode*, std::string>> stack;
stack.push({root, ""});
while (!stack.empty()) {
auto [node, currentPath] = stack.top();
stack.pop();
if (node->isEndOfWord) {
std::cout << "{" << currentPath << "}" << std::endl;
}
for (const auto& [ch, childNode] : node->children) {
stack.push({childNode, currentPath.empty() ? std::string(1, ch) : currentPath + "." + ch});
}
}
}
int main() {
TrieNode* root = new TrieNode();
root->children['a'] = new TrieNode("a");
root->children['a']->children['b'] = new TrieNode("a.b");
root->children['a']->children['b']->isEndOfWord = true;
root->children['c'] = new TrieNode("c");
root->children['c']->isEndOfWord = true;
printTrie扁平化名称空间(root);
// 清理分配的内存
// 这里省略了内存清理的代码,实际应用中需要确保释放所有分配的内存
return 0;
}
这段代码定义了一个TrieNode
结构体,用于表示trie树的节点。每个节点包含一个子节点的哈希映射、一个标志位表示是否是单词的结尾,以及一个前缀字符串。
printTrie扁平化名称空间
函数使用了一个栈来迭代地遍历trie树。每次从栈中取出一个节点时,它会检查该节点是否是单词的结尾,如果是,则打印出当前的路径。然后,它会将该节点的所有子节点推入栈中,同时更新路径字符串。
这个解决方案的优势在于它避免了递归调用可能导致的栈溢出问题,并且可以很容易地适应大型trie树。
应用场景包括:
如果你遇到了问题,比如打印出的结构不正确或者程序崩溃,可能的原因包括:
解决这些问题的方法包括:
参考链接:
领取专属 10元无门槛券
手把手带您无忧上云