summaryrefslogtreecommitdiff
path: root/sources
diff options
context:
space:
mode:
authorHaidong Ji2019-06-09 16:51:07 -0500
committerHaidong Ji2019-06-09 16:51:07 -0500
commit560bb4c29cbbfd940e2773df0ff28d0315b16517 (patch)
tree6eb96446b793232217facd14e311ddd25e2e54c7 /sources
parent151a820c72161aacde623b444ab1f137689a36f5 (diff)
tree traversal done (in/pre/post) orders
Not too bad since I worked it out in Java first
Diffstat (limited to 'sources')
-rw-r--r--sources/tree_traversal.py126
1 files changed, 126 insertions, 0 deletions
diff --git a/sources/tree_traversal.py b/sources/tree_traversal.py
new file mode 100644
index 0000000..b75b0f7
--- /dev/null
+++ b/sources/tree_traversal.py
@@ -0,0 +1,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)))