Лес из узлов дерева C ++?

Question

Эй, я пытаюсь создать "лес" из узлов дерева. Пользователь введет два леса. Например,
Forest1:
а
_ _b
с

где b - дочернее дерево / узел a.
Forest2:
д
е
_ _f
_ _ _ _g
_ _h

, где d - родитель, e - родитель f, а h, f - родитель g. f и h родные братья.

В любом случае, у меня есть два вопроса, над которыми я застрял некоторое время:
Каков наилучший способ получить этот ввод (из системы Unix?) Построчно?
И, каков наилучший способ пройти через это, чтобы получить родителей и детей.
Любые другие советы также приветствуются, спасибо!

Answer 1

Вы можете использовать Lisp-подобный синтаксис для ввода:

(a (b)) (c)

(d) (e (f (g)) (h))

Я использовал библиотеку Boost.Graph для аналогичных целей.Это очень хорошая реализация, но она требует скромного времени, чтобы ознакомиться с ней.

Answer 2

Не имеет большого значения, в какой системе вы находитесь, но да, обрабатывайте ее построчно, используя ifstream. Я не думаю, что существует «лучший способ» пройти через это, поскольку это текстовый файл, и кто-то может передать вам текстовый файл, отформатированный любым странным способом; поэтому вы должны учитывать это и стараться как можно лучше обрабатывать все случаи.

Итак, давайте попробуем шагнуть через, как вы можете это сделать.

Вы находитесь в цикле, обрабатывающем эту строку построчно, ваш текущий узел имеет значение NULL, так как родительский объект еще не обработан. Прочитайте в строке и найдите подчеркивание в начале строки; если parent равен null, то у нас есть строка, которую невозможно обработать, поэтому пропустите ее. Если первый символ не является подчеркиванием, установите его для текущего родительского узла и перейдите к следующей части цикла. Если есть подчеркивание и текущий родитель не равен нулю, то итерируйте оставшееся количество подчеркиваний и переберите потомков узлов внутри родителя.

На самом деле, у меня просто была идея получше, но это даст вам, по крайней мере, подумать. Приветствия, дайте мне знать, что вы придумали.

Answer 3

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

Если ваше дерево не является двоичным (то есть узел может иметь более 2 дочерних элементов), возможно, стоит ввести «виртуальный» родительский узел, который имеет все действительные корни в качестве дочерних узлов. Это исключит некоторые раздражающие особые случаи (например, лес пуст), особенно при обходе.

Возможно, было бы хорошо добавить указатель от потомка к родителю; если вы хотите поддерживать итераторы в вашем дереве, это будет полезно. Однако, если вам не нужны сложные действия во время обхода, вы можете реализовать их рекурсивно, и тогда вам не нужны какие-либо указатели типа «ребенок-родитель».