有没有一种好方法可以在 C++11 中打印出 JSON-like trie 结构（仅限迭代解决方案）的展平命名空间？

Question

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

我想遍历我的 trie，以便我以迭代方式打印出给定节点的 "flattened" 路径。

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

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

    };

如果我通过以下方式添加 children：

    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

将递归过程转换为交互过程的技巧是使 'pending work' 明确。在您的情况下，一个工作单元是一个 TreeNode 和一个前缀，工作单元保存在 std::stack 中（因为您的递归解决方案是 depth-first）。任何（以前的）递归调用都必须将工作添加到堆栈，并且在没有更多工作可用时停止工作。

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

Answer 2

完全避免使用堆栈的一种方法是在树中使用父指针。

你的迭代器可以追下树，处理底部分支中的所有对等节点，然后使用最后一个节点中的父指针返回上一层，移动到该级别的下一个对等节点, 再往下走。归根结底是一个比较精简的算法。

当然，对于一棵大树，每个节点上的父指针的成本比显式堆栈的成本/多/多，但如果您对父指针有其他用途，则值得考虑。

有没有一种好方法可以在 C++11 中打印出 JSON-like trie 结构（仅限迭代解决方案）的展平命名空间？

Is there a good way to print out a flattened namespace for a JSON-like trie structure (iterative solution only) in C++11?

c++

c++11

dictionary

traversal

trie