Форум программистов
 
Регистрация на форуме тут, о проблемах пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль

Вернуться   Форум программистов > Скриптовые языки программирования > Python
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме 15-35 тыс рублей в месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 24.11.2021, 17:48   #1
polin11
Форумчанин
 
Регистрация: 07.06.2015
Сообщений: 144
По умолчанию прямой обход дерева

Есть словарь, ключ - ид. узла, значение словаря - массив ид. детей у данного узла
Код:
{313: [346, 349], 346: [350], 0: [313, 312], 312: [348]}
Получается такое n-арное дерево

Код:
level 1                    0
level 2           313            312 
level 3     346        349             348     
level 4   350
Нужно сделать прямой обход такого дерева, получить массив словарей, где ключ словаря это ид. узла,
а значение словаря уровень иерархии.

Такой результат:
Код:
   [{0:1}, {313:2}, {346:3}, {349:3}, {312:2}, {348:3}]
Стал заморачиваться, писать классы для реализации дерева и его обхода, но запутался.
Может кто знает более простой алгоритм для реализации, либо библиотеку питона, которую можно использовать
polin11 вне форума Ответить с цитированием
Старый 24.11.2021, 18:14   #2
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 6,465
По умолчанию

Код:
def nlr(tree, levels, node = 0, level = 1):
    levels.append({node: level})
    for subnode in tree.get(node, []):
        nlr(tree, levels, subnode, level + 1)

tree = {313: [346, 349], 346: [350], 0: [313, 312], 312: [348]}
levels = []
nlr(tree, levels)
print(levels)
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA на форуме Ответить с цитированием
Ответ
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Windows Forms - как переделать чтобы был обход в ширину бинарного дерева (в том что нашел обход в глубину) Audax_Rogerus Windows Forms 0 17.07.2020 08:36
Бинарное дерево (прямой и обратный обход) JonnyFletcher Помощь студентам 0 26.05.2013 12:48
Обход дерева mohita C# (си шарп) 1 11.12.2011 18:48
Создание и обход дерева jonni2008 Общие вопросы .NET 1 12.11.2010 06:05
обход дерева ribka Помощь студентам 2 11.12.2007 20:38

Реклама для незарегистрированных, регистрация на форуме