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
|
# python3
import queue
import sys
def in_order(key, left, right):
keyIndexStack = []
result = []
walkLeft = True
currentIndex = 0
keyIndexStack.append(currentIndex)
while len(keyIndexStack) != 0 or right[currentIndex] != -1:
if walkLeft:
if left[currentIndex] != -1:
currentIndex = left[currentIndex]
keyIndexStack.append(currentIndex)
else:
result.append(key[keyIndexStack.pop()])
walkLeft = False
else:
if right[currentIndex] != -1:
currentIndex = right[currentIndex]
keyIndexStack.append(currentIndex)
walkLeft = True
else:
if len(keyIndexStack) != 0:
currentIndex = keyIndexStack.pop()
result.append(key[currentIndex])
return result
def pre_order(key, left, right):
keyIndexStack = []
keyIndexQueue = queue.Queue()
result = []
walkLeft = True
currentIndex = 0
keyIndexStack.append(currentIndex)
keyIndexQueue.put(currentIndex)
while len(keyIndexStack) != 0 or right[currentIndex] != -1:
if walkLeft:
if left[currentIndex] != -1:
currentIndex = left[currentIndex]
keyIndexQueue.put(currentIndex)
keyIndexStack.append(currentIndex)
else:
keyIndexStack.pop()
walkLeft = False
result.append(key[keyIndexQueue.get()])
else:
if right[currentIndex] != -1:
currentIndex = right[currentIndex]
keyIndexQueue.put(currentIndex)
keyIndexStack.append(currentIndex)
walkLeft = True
else:
if len(keyIndexStack) != 0:
currentIndex = keyIndexStack.pop()
result.append(key[keyIndexQueue.get()])
return result
def post_order(key, left, right):
keyIndexStack = []
peekedSet = set([])
result = []
walkLeft = True
currentIndex = 0
keyIndexStack.append(currentIndex)
while len(keyIndexStack) != 0:
if currentIndex in peekedSet:
result.append(key[currentIndex])
peekedSet.remove(currentIndex)
keyIndexStack.pop()
if len(keyIndexStack) == 0:
break
currentIndex = keyIndexStack[-1]
continue
if walkLeft:
if left[currentIndex] != -1:
currentIndex = left[currentIndex]
keyIndexStack.append(currentIndex)
else:
if right[currentIndex] == -1:
result.append(key[currentIndex])
walkLeft = False
keyIndexStack.pop()
currentIndex = keyIndexStack[-1]
else:
peekedSet.add(currentIndex)
currentIndex = right[currentIndex]
keyIndexStack.append(currentIndex)
else:
if right[currentIndex] != -1:
peekedSet.add(currentIndex)
currentIndex = right[currentIndex]
keyIndexStack.append(currentIndex)
walkLeft = True
else:
result.append(key[currentIndex])
i = keyIndexStack.pop();
if i != currentIndex:
result.append(key[i])
if len(keyIndexStack) == 0:
break
currentIndex = keyIndexStack[-1]
return result
if __name__ == '__main__':
n = int(sys.stdin.readline())
key = [0 for i in range(n)]
left = [0 for i in range(n)]
right = [0 for i in range(n)]
for i in range(n):
[a, b, c] = map(int, sys.stdin.readline().split())
key[i] = a
left[i] = b
right[i] = c
print(" ".join(str(x) for x in in_order(key, left, right)))
print(" ".join(str(x) for x in pre_order(key, left, right)))
print(" ".join(str(x) for x in post_order(key, left, right)))
|
