#!/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()
def tree_walk(self, level=0): # выводим всё дерево начиная с уровня 0. Обход в ширину
res = [self.root,] # res - уровень, который нужно вывести в данный момент
while res:
res1 = []
for el in res:
yield el
res1 += el.children
res = res1
def level(self, level=0): # выведем узлы заданного уровня
if level == 0:
yield self.root
else:
res = [self.root,]
for i in xrange(level-1):
res1 = []
for el in res:
res1 += el.children
res = res1
for el in res:
for ch in el.children:
yield ch
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)]
print
print 'Выведем "for i in tree.tree_walk(): print i"'
for i in tree.tree_walk():
print i
print
print 'Выведем первый уровень дерева (tree.level(1)):'
print [str(x) for x in tree.level(1)]
print 'Выведем второй уровень дерева (tree.level(1)):'
print [str(x) for x in tree.level(2)]