usr bin python coding utf-8 class Node def __init__ self parent childr

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#!/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)]