I'm attempting to create a trie structure in C++, where each node holds a name, and some data, and can hold references to children nodes of any number.
I'd like to traverse my trie such that I print out the "flattened" path to a given node in an iterative fashion.
Given some Tree where a node is defined by:
class Node
{
public:
virtual std::string node_name() = 0;
};
class TreeNode : Node
{
public:
std::string name;
std::map<std::string, TreeNode&> children {};
TreeNode(const std::string&name) : name(name) {}
std::string node_name()
{
return name;
}
void add_child(TreeNode& node)
{
children.insert(std::pair<std::string, TreeNode&>
(node.node_name(), node));
}
};
If I add children via:
TreeNode root { "root" };
TreeNode a { "a" };
TreeNode b { "b" };
TreeNode c { "c" };
TreeNode d { "d" };
TreeNode e { "e" };
a.add_child(c);
a.add_child(d);
b.add_child(e);
root.add_child(a);
root.add_child(b);
// flatten the tree and print out the namespace here
flatten(root);
The output should be (don't care about order):
root
root.a
root.a.c
root.a.d
root.b
root.b.e
I've already implemented the recursive solution (see below), but I'd like to know if there's a way to do this iteratively (since I'd like to avoid recursion if possible in my application).
Here is the recursive version:
void flatten_helper(TreeNode& root,
const std::string& prefix)
{
static const std::string delimeter { "." };
std::string namespace_path(prefix);
if (!prefix.empty())
{
namespace_path.append(delimeter);
}
namespace_path.append(root.node_name());
for (auto& node : root.children)
{
flatten_helper(node.second, namespace_path);
}
// do something with node/complete namespace name
std::cout << namespace_path << std::endl;
}
void flatten(TreeNode& node)
{
std::string empty {""};
return flatten_helper(node, empty);
}
int main(int argc, char** argv)
{
TreeNode root { "root" };
TreeNode a { "a" };
TreeNode b { "b" };
TreeNode c { "c" };
TreeNode d { "d" };
TreeNode e { "e" };
a.add_child(c);
a.add_child(d);
b.add_child(e);
root.add_child(a);
root.add_child(b);
flatten(root);
return 0;
}
I'm a bit stumped on how to approach the iterative version in c++11 (have tried a few iterations of various tree traversals) - any help would be appreciated.
Aucun commentaire:
Enregistrer un commentaire