c++ - 有没有一种好方法可以在 C++11 中打印出类似 JSON 的 trie 结构(仅限迭代解决方案)的扁平命名空间？

Question

我试图在 C++ 中创建一个 trie 结构，其中每个节点都包含一个名称和一些数据，并且可以包含对任意数量的子节点的引用。

我想遍历我的 trie，以便以迭代方式打印出到给定节点的“扁平化”路径。

给定一些树，其中节点定义为:

    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));
        }

    };

如果我通过以下方式添加 child :

    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);

输出应该是(不关心顺序):

    root
    root.a
    root.a.c
    root.a.d
    root.b
    root.b.e

我已经实现了递归解决方案(见下文)，但我想知道是否有一种方法可以迭代地执行此操作(因为我想尽可能避免在我的应用程序中使用递归)。

这是递归版本:

    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;
    }

我对如何处理 c++11 中的迭代版本有点困惑(尝试了几次各种树遍历的迭代)- 任何帮助将不胜感激。

Answer 1

将递归过程转换为交互过程的诀窍是明确“待处理的工作”。在您的情况下，一个工作单元是一个 TreeNode 和一个前缀，并且工作单元保存在一个 std::stack 中(因为您的递归解决方案是深度优先的).任何(以前的)递归调用都必须将工作添加到堆栈，并且在没有更多工作可用时停止工作。

void flatten_iter(TreeNode& root_node)
{
    using WorkItem = std::pair<TreeNode&, std::string>;
    static const std::string delimeter{ "." };

    std::stack<WorkItem> workitems;
    workitems.emplace(root_node, "");

    while (!workitems.empty()) {
        auto [ node, prefix ] = workitems.top();
        workitems.pop();

        std::string namespace_path(prefix);
        if (!prefix.empty())
        {
            namespace_path.append(delimeter);
        }

        namespace_path.append(node.node_name());

        for (auto& child : node.children)
        {
            workitems.emplace(child.second, namespace_path);
        }

        // do something with node/complete namespace name
        std::cout << namespace_path << std::endl;
    }
}