Учитывая список ответвлений, как найти список древовидного списка, которые являются односвязными вместе
Скажем, у меня есть список ответвлений, как найти список древовидного списка, которые являются односвязными вместе? Ниже схемы должен проиллюстрировать мой тезис. Вход является списком ответвлений в единственном дереве, как маркировано, т.е. 1, 2, 3 и так далее
1
задан Community 8 February 2017 в 14:24
поделиться
2 ответа
Процесс выглядит следующим образом:
- Создайте функцию, которая принимает узел дерева в качестве параметра
- Если узел не имеет дочерних элементов, распечатайте значение текущего узла и возврат.
- Если узел имеет двух дочерних узлов, завершите текущий список значений одного узла, затем перейдите к левому узлу, а затем к правому узлу
- Если узел имеет одного дочернего элемента, добавьте его в список значений, содержащихся в дерево, затем перейдите в этот узел.
- Продолжайте.
1
ответ дан 3 September 2019 в 01:07
поделиться
Судя по изображению, существует действительно простое решение. Давайте составим список с элементами, которые являются списками одного типа. Процедура будет называться tree_lists (список, дерево). Все, что вам нужно сделать, это:
- Глядя на текущее соединение, у вас есть указатель списка на первом элементе списка.
- Если есть
более одного дочернего элемента в текущем узле: выполнить итерацию по каждому поддереву
, увеличивая указатель на список
и вызывая
{{ 1}} tree_lists (list [i], current_subtree) где i - указатель на список, а current_subtree - это текущее поддерево =) - Если существует только один дочерний элемент, просто добавьте это соединение с текущим элементом списка и перейти к следующему.
- Конечно, указатель списка и значения списка должны быть каким-то образом глобальными и также изменяться в рекурсии.
1
ответ дан 3 September 2019 в 01:07
поделиться
Другие вопросы по тегам: