Есть ли хороший способ распечатать сглаженное пространство имен для структуры дерева, подобной JSON (только итеративное решение) в C ++ 11?

Question

Я пытаюсь создать структуру дерева в C ++, где каждый узел содержит имя и некоторые данные, и может содержать ссылки на дочерние узлы любого числа.

Я хотел бы пройтись по моей схеме, чтобы я распечатал «сплющенный» путь к данному узлу итеративным способом.

Для некоторого дерева, где узел определяется с помощью:

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

    };

Если я добавлю детей через:

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

Answer 2

Один из способов вообще избежать использования стека - это иметь родительские указатели в вашем дереве.

Ваш итератор может преследовать дерево, обрабатывать все одноранговые узлы в нижней ветви, а затем использовать родительский указатель в последнем узле, чтобы вернуться на 1 уровень, перейти к следующему одноранговому узлу на этом уровне и спустись снова. В конце концов, это относительно минимальный алгоритм.

Конечно, при большом дереве стоимость родительских указателей на каждом узле / намного / больше стоимости явного стека, но если у вас есть другое использование родительских указателей, стоит подумать.