рекурсивное генеалогическое дерево с объектами - PullRequest
Новая
       23

рекурсивное генеалогическое дерево с объектами

0 голосов
/ 27 ноября 2018

Здравствуйте, ребята. Мне нужна помощь с рекурсивным представлением генеалогического древа, вот данные: 

children_and_parents = {
"Mary": ["Patricia", "Lisa"], 
"Patricia": ["Barbara", "Helen", "Maria"], 
"Maria": ["Keren", "Carol"], 
"Barbara": ["Betty"]
}

Я должен упомянуть, что значения являются объектами, поэтому мне нужно назвать их children_and_parents ["Maria"] .child - чтобы получить ['Patricia', 'Lisa']

рекурсивную программу, которая у меня сейчас есть 

def draw_family_tree(person, level=0):
if person in children_and_parents:
    for i in range (len(children_and_parents[person].child)):
        print (" "*level, person)
        return draw_family_tree(children_and_parents[person].child[i], level+3)

, то, что она сейчас делает, 

Mary
   Patricia
      Barbara

но результат должен быть примерно таким: 

Mary
   Patricia
       Barbara
           Betty
       Helen
       Maria
           Keren
           Carol
   Lisa

, поэтому я застрял в самом начале программы, если кто-то захочет помочь, я буду очень признателен

приблизительный код https://repl.it/repls/BlondCavernousExponents

1 Ответ

0 голосов
/ 27 ноября 2018

Поиск корня дерева является хорошим кандидатом для отдельной операции.В вашем примере мы знаем, что это "Mary", поэтому мы можем выполнить итерацию соответственно.Если мы не знаем (и небезопасно предполагать, что первым элементом в dict является корень), вы можете написать: 

def find_root(tree):
    children = set([x for y in tree.values() for x in y])

    for k in tree.keys():
        if k not in children:
            return k

Что касается самой процедуры печати, попробуйте распечатать родительский узел до того, какперебирая детей.Я также рекомендую передать дерево в качестве параметра в функцию, чтобы сохранить инкапсуляцию и сохранить ее возможность многократного использования (т. Е. Не зависит от некоторой переменной с именем children_and_parents, существующей в области вызова. 

def draw_family_tree(tree, root, level=0, gap=3):
    if root:
        print(" " * level + root)

        if root in tree:
            for child in tree[root]:
                draw_family_tree(tree, child, level + gap)

Вывод: 

Mary
   Patricia
      Barbara
         Betty
      Helen
      Maria
         Keren
         Carol
   Lisa

Попробуйте!

Как упоминалось в предыдущем обсуждении, я не рекомендую использовать класс для простой пары <string, list>, он добавляет много многословиябез функциональности и на самом деле немного вводит в заблуждение, потому что parent вводит в заблуждение, предполагает, что у человека есть родитель (это на самом деле относится к имени человека, представленного объектом). Если вы решите пойти по этому пути, вам нужно будетдобавьте .child ко всем доступам к массиву и напишите функцию __repr__(self) для вашего класса (или print(root.parent).

...