Кружок по программированию, 2017-2018

В языке Python для этой задачи есть очень удобные для этого структуры — словари и множества. Будем хранить два словаря — parents и children. В каждом словаре в качестве ключей будут участвовать все вершины дерева и только они. Пусть A — некоторая вершина. Тогда parents[A] — это предок этой вершины, либо None для корня. А children[A] — это множество всех потомков этой вершины. Также корень дерева будем хранить в переменной root.

Например, дерево с картинок выше будем хранить так:

root = 'Jake'
children = {'Jake': {'Alice', 'Caitlin'},
            'Alice': {'Adam', 'Grace', 'Jay', 'Sean'},
            'Caitlin': {'Ben'},
            'Adam': set(),
            'Grace': {'Luca'},
            'Jay': set(),
            'Sean': set(),
            'Ben': {'Megan', 'Eva', 'Harry'},
            'Megan': set(),
            'Eva': set(),
            'Harry': set(),
            'Luca': set(),
            }
parents = {'Jake': None,
           'Alice': 'Jake',
           'Caitlin': 'Jake',
           'Adam': 'Alice',
           'Grace': 'Alice',
           'Jay': 'Alice',
           'Sean': 'Alice',
           'Ben': 'Caitlin',
           'Eva': 'Ben',
           'Harry': 'Ben',
           'Megan': 'Ben',
           'Luca': 'Grace',
           }

Такой способ хранения, вообще говоря, избыточен. По словарю children можно восстановить словарь parents и наоборот. И по любому из этих словарей можно найти корень. Однако он достаточно удобен.