Как добавить элемент из файла в ветвящееся дерево?

Question

[Константин Подыганов]

Пишу программку для составления генеалогического древа с помощью деревьев (графы не являются решением)

Есть структура ветвящегося дерева:

struct TreeNode {
    std::string name;
    std::vector<TreeNode*> child;
};

Так же функция для добавления которая принимает TreeNode и строку для указания имени.

Как реализовать добавление из файла путем следующей структуры?

иван
 алексей
  игорь
 андрей
  роман
  кирилл

Answer 1

[Wataru]

Самый простой вариант - поддерживать вектор из указателей на самые правые узлы во всех доступных уровнях.

Сначала читаете первую строку и создаете из нее корень дерева.

А потом в цикле читайте строку и считайте, сколько там пробелов. Их должно быть не больше, чем количество доступных уровней (т.е. элементов в векторе).
Добавляете текущую строку к узлу, который на уровне равном количеству пробелов (-1, потому что индексация с 0). Укорачиваете вектор до этого узла (все с уровенем ниже та вершина, к которой добавили ребенка - уже недоступно). Добавляете в вектор указатель на только что добавленную вершину.

В вашем примере.

Прочитали иван, сделали корень дерева. Вектор будет {"иван"} (указатель на вершину-корень дерева).

Прочитали алексей. 1 проблел - все хорошо, в векторое 1 элемент, значит может быть до 1 пробела. Добавили "алексей" к вершине "иван". Вектор {"иван", "алексей"}

Прочитали игорь. Вектор стал {"иван", "алексей", "игорь"}.

Прочитали андрей. 1 пробел. Может быть до трех пробелов, ведь в векторе 3 элемента. Добавили "андрей" к узлу из вектора по индексу 0 (-1 к количеству пробелов). обрезали вектор до длины 1 и добавили туда новую вершину. Вектор стал {"иван", "андрей"}

И т.д.

Для добавления вершины создайте новый TreeNode с нужной строкой и push_back в список детей для нужного отца.