/
my_generic_tree.py
97 lines (71 loc) · 3.35 KB
/
my_generic_tree.py
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
class Generic_tree_Node:
def __init__(self, data):
# inorder thread binary tree
self.data = data
self.nextsibling = None
self.firstchild = None
class Generic_tree:
def __init__(self, node_arr):
self.root = None
for i, family in enumerate(node_arr):
print('try to insert', family, 'in step ', i)
self.insert(i, family)
def insert(self, i, family):
if self.root is None:
print('make root node')
self.root = Generic_tree_Node(family[0][0])
print('make first child which is {} for root'.format(family[0][1]))
self.root.firstchild = Generic_tree_Node(family[0][1])
temp_node = self.root.firstchild
siblings = [contents[1] for contents in family[1:]] #family のfirstchildはsiblingから除く
print('insert siblings to root.firstchild')
for sibling in siblings:
temp_node.nextsibling = Generic_tree_Node(sibling)
temp_node = temp_node.nextsibling
print('------------------------------')
else:
if i >=1:
pairent = family[0][0]
child = family[0][1]
flag = True
next_queue = [self.root] #初回のqueueを作成
while flag:
temp_queue, next_queue = next_queue, []
for node in temp_queue:
if node.nextsibling is not None:
# print('insert siblings to ', node.data, 'for making queue')
next_queue.append(node.nextsibling)
if node.firstchild is not None:
# print('insert firstchild to ', node.data, 'for making queue')
next_queue.append(node.firstchild)
if node.data == pairent:
print('when you find {} which is pairent, insert '.format(node.data), child, ' as firstchild.')
node.firstchild = Generic_tree_Node(child)
temp_node = node.firstchild
print('insert siblings to ', node.data, '.')
siblings = [contents[1] for contents in family[1:]] #family のfirstchildはsiblingから除く
for sibling in siblings:
temp_node.nextsibling = Generic_tree_Node(sibling)
temp_node = temp_node.nextsibling
print('------------------------------')
if len(next_queue) == 0:
flag = None
def inorder_traverse(self, node):
# 走査の終了条件
if node is None:
return
self.inorder_traverse(node.nextsibling)
print(node.data)
self.inorder_traverse(node.firstchild)
#####
node_arr =[
[[1, 2], [1, 3], [1, 4], [1, 5],[1, 6]],
[[4, 9]],
[[5, 10], [5, 11]],
[[6, 7], [6, 8], [6, 12], [6, 13], [6, 14]],
[[8, 15]],
[[11, 16], [11, 17]]
]
ins_generic = Generic_tree(node_arr)
print(ins_generic.root.data)
ins_generic.inorder_traverse(ins_generic.root.firstchild)