#!/usr/bin/python # coding: utf-8 class Node: def __init__(self, parent, children): self.parent = parent self.children = children def output(self, depth=0): # составляем строку (поиском в глубину), чтобы её можно было вывести на экран res = ' '*depth + str(self) for ch in self.children: res += '\n' + ch.output(depth+4) # 4 - кол-во пробелов, которыми делается отступ return res def append_child(self): node = Node(self, []) self.children.append(node) return node def path_to_root(self): if self.parent: return [self,] + self.parent.path_to_root() else: return [self] def path_to_node(self, node): pth1 = self.path_to_root() pth2 = node.path_to_root() pth1.reverse() pth2.reverse() if pth1[0] != pth2[0]: return None pth1 += [1,] pth2 += [2,] lca = 0 while pth1[lca] == pth2[lca]: lca += 1 pth1.reverse() res = pth1[1:len(pth1)-lca+1] + pth2[lca:-1] return res def leaves(self): res = [] for ch in self.children: if ch.children: res += ch.leaves() else: res.append(ch) return res class Tree: def __init__(self, root): # root - объект типа Node self.root = root def output(self): return self.root.output() class GenNode(Node): def __init__(self, parent, name): Node.__init__(self, parent, []) self.name = name def __str__(self): return self.name def append_child(self, name): node = GenNode(self, name) self.children.append(node) return node def get_brothers(self): res = [] if self.parent: res = self.parent.children return res def get_uncles(self): res = [] grandfather = self.get_grandfather() if grandfather: res = [x for x in grandfather.children if x != self.parent] return res def get_grandfather(self): res = None if self.parent: if self.parent.parent: res = self.parent.parent return res def get_grandchildren(self): res = [] for ch in self.children: for gch in ch.children: res.append(gch) return res class GenTree(Tree): pass # Итак, демонстрация rickard = GenNode(None, 'Rickard Stark') eddard = rickard.append_child('Eddard Stark') brandon = rickard.append_child('Brandon Stark') benjen = rickard.append_child('Benjen Stark') robb = eddard.append_child('Robb Stark') bran = eddard.append_child('Bran Stark') rickon = eddard.append_child('Rickon Stark') jon = eddard.append_child('Jon Snow') tree = Tree(rickard) print 'Выведем всё древо:' print print tree.output() print print 'Выведем братьев Эддарда:' for x in eddard.get_brothers(): print x print print 'Выведем внуков Рикарда:' for x in rickard.get_grandchildren(): print x print print 'Выведем дедушку Джона Сноу:' print jon.get_grandfather() print print 'Выведем дядь Джона Сноу:' for x in jon.get_uncles(): print x print print 'Выведем jon.path_to_root():' print [str(x) for x in jon.path_to_root()] print print 'Выведем rickard.leaves():' print [str(x) for x in rickard.leaves()] print print 'Выведем jon.path_to_node(benjen):' print [str(x) for x in jon.path_to_node(benjen)]