Поиск слова для “выравнивания дерева”
Я задаюсь вопросом, существует ли существующее слово для описания процесса, который я в настоящее время использую. Я хочу назвать его "выравниванием дерева", но я чувствую, что должно быть лучшее слово или фраза.
вход:
|--D
--B
| |--C
|
A-E
|
| |--G
--F
|--H
вывод:
[ [A, B, D]
[A, B, C]
[A, E]
[A, F, G]
[A, F, H] ]
Существует ли установленное название этого процесса?
9 ответов
Перечисление путей?
Обход DFS?
или моя любимая
Массивы дерева!
Как насчет 'Hydrating' (или DeHydrating) в зависимости от ситуации?
Я бы сказал, что вы просто обходите дерево, сохраняя путь к текущему узлу. Когда вы посещаете лист, вы печатаете полный путь к нему.
Я не думаю, что есть конкретное название, но это не сильно отличается от очень простого обхода.
Вам нужен поиск в глубину, чтобы захватить каждый путь из корень к листу.
Псевдокод:
global allPaths = []
R = root
currentPath = []
findPaths(R, currentPath)
findPaths(R, currentPath){
if R has no children,
allPaths.add( currentPath )
else
for each child C in R:
findPaths(C, currentPath + R)
}
Де-нормализация, казалось бы, лучше всего. Потому что действительно, если вы заметите вашу новую структуру, у вас есть избыточные данные, и это, похоже, напрямую соответствует концептуальной идее.
Если входными данными является дерево, а выходными данными список цитируемых вами списков, вы на самом деле ищете не фразу для процесса , а имя для подпрограмму вы вызываете. И имя такой подпрограммы должно быть описанием того, что она возвращает .
Как насчет RootPathsOfLeaves ? или его переделка ...