LINUX.ORG.RU

История изменений

Исправление dissident, (текущая версия) :

Может просто превратить его в lisp (рекурсивно обходя DFS'ом), а потом собрать обратно, при каждой новой скобочке создавая нового child'а. Тут пример: https://www.geeksforgeeks.org/construct-binary-tree-string-bracket-representa... (только по-моему это можно сделать проще).

Для упрощения может описать дерево так? Или сконвертировать его на такой формат (а потом при десериализации можно обратно).

template<class PayloadPlusIdPlusWhatever>
struct Tree {
    PayloadPlusIdPlusWhatever data;
    ListOrVectorOrWhatever<Tree*> children;
}

string tree_to_string(Tree *)
   sstream s;
   ss << data;
   for (Tree* child: children) {
       ss << "("
       ss << tree_to_string(child);
       ss << "(";
   }
   return ss.to_str();
}

Псевдокод десериализации:

// this is pseudocode, don't care about leaks or whatever
// call with curr != null but an allocated root
Tree* string_to_tree(string s, Tree *curr=null)
{
    string data_or_bracket = get_and_remove_data_or_bracket(s);
    if (is_data(data_or_bracket) && curr != null)
    {        
        curr->data = data_or_bracket;        
    }
    else if (is_opening_bracket(data_or_bracket) && curr != null)
    {
        Tree* t = new Tree();
        curr->children.push_back(t);
    }
    else if (is_closing_brackest(data_or_bracket)
    {
        return;
    }
    string_to_tree(s, curr);
}

Disclaimer: не тестировал и даже особо не думал.

PS Если важно, чтобы данные выглядели именно так как выглядят и жалко памяти создавать временные структуры где есть parent и список детей, тогда наверное придется писать как есть, т.е. {id,parent_id},{id,parent_id}, но тогда с другой стороны десериализация будет требовать дополнительных структур как показал MetalBeaver.

Исходная версия dissident, :

Может просто превратить его в lisp (рекурсивно обходя DFS'ом), а потом собрать обратно, при каждой новой скобочке создавая нового child'а. Тут пример: https://www.geeksforgeeks.org/construct-binary-tree-string-bracket-representa... (только по-моему это можно сделать проще).

Для упрощения может описать так?

template<class PayloadPlusIdPlusWhatever>
struct Tree {
    PayloadPlusIdPlusWhatever data;
    ListOrVectorOrWhatever<Tree*> children;
}

string tree_to_string(Tree *)
   sstream s;
   ss << data;
   for (Tree* child: children) {
       ss << "("
       ss << tree_to_string(child);
       ss << "(";
   }
   return ss.to_str();
}

Псевдокод десериализации:

// this is pseudocode, don't care about leaks or whatever
// call with curr != null but an allocated root
Tree* string_to_tree(string s, Tree *curr=null)
{
    string data_or_bracket = get_and_remove_data_or_bracket(s);
    if (is_data(data_or_bracket) && curr != null)
    {        
        curr->data = data_or_bracket;        
    }
    else if (is_opening_bracket(data_or_bracket) && curr != null)
    {
        Tree* t = new Tree();
        curr->children.push_back(t);
    }
    else if (is_closing_brackest(data_or_bracket)
    {
        return;
    }
    string_to_tree(s, curr);
}

Disclaimer: не тестировал и даже особо не думал.

PS Если важно, чтобы данные выглядели именно так как выглядят и жалко памяти создавать временные структуры где есть parent и список детей, тогда наверное придется писать как есть, т.е. {id,parent_id},{id,parent_id}, но тогда с другой стороны десериализация будет требовать дополнительных структур как показал MetalBeaver.