-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary_tree.py
166 lines (132 loc) · 5.32 KB
/
binary_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
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
154
155
156
157
158
159
160
161
162
163
164
165
166
from src.data_structures.queue import Queue
class BinaryTreeNode:
__unassigned = -1
@classmethod
def buildTree(self, inorder, postorder):
if inorder:
ind = inorder.index(postorder.pop())
root = BinaryTreeNode(inorder[ind])
root.right = self.buildTree(inorder[ind+1:], postorder)
root.left = self.buildTree(inorder[:ind], postorder)
return root
@classmethod
def construct_from_in_and_post_orders(self, in_order, post_order):
return BinaryTreeNode.buildTree(in_order, post_order)
if(len(in_order) == 0):
return None
if(len(in_order) == 1):
return BinaryTreeNode(in_order[0])
# Assume that duplicates do not exist in the tree.
# root is always the last node in post_order
root = post_order.pop()
root_index_in_order = in_order.index(root)
# thus we can split in_order on the root
in_left = in_order[:root_index_in_order]
in_right = in_order[root_index_in_order + 1:]
# recurse
right_tree = BinaryTreeNode.construct_from_in_and_post_orders(
in_right, post_order)
left_tree = BinaryTreeNode.construct_from_in_and_post_orders(
in_left, post_order)
# put it together
tree = BinaryTreeNode(root)
tree.left, tree.right = left_tree, right_tree
return tree
@classmethod
def __node_for_construction(self, data):
if(data is None):
return data
node = BinaryTreeNode(data)
node.left = self.__unassigned
node.right = self.__unassigned
return node
@classmethod
def construct_from_list(self, list):
"""
Creates a binary tree from a level-ordered list of values.
Empty children for existing nodes should be specified with
None.
e.g. [4,7,3,None,None,1] yields a tree of shape:
4
/ \
7 3
/
1
"""
queue = Queue()
root = self.__node_for_construction(list[0])
current = root
for data in list[1:]:
new = self.__node_for_construction(data)
if new is not None:
queue.enqueue(new)
if(current.left == self.__unassigned):
current.left = new
elif(current.right == self.__unassigned):
current.right = new
else: # current node is full
current = queue.dequeue()
current.left = new
# clean up (ensure unassigned values are represented as None)
queue = Queue()
queue.enqueue(root)
while(not queue.is_empty()):
current = queue.dequeue()
if(current.left == self.__unassigned):
current.left = None
elif(current.left):
queue.enqueue(current.left)
if(current.right == self.__unassigned):
current.right = None
elif(current.right):
queue.enqueue(current.right)
return root
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def _traverse_default_wrapper(self, traverse_fn):
# append to this array as we traverse the tree
arr = []
def default_traverse_step(*args):
return arr.append(args[0])
# now call the appropriate traverse function
traverse_fn(default_traverse_step, arr)
return arr
def traverse_in_order(self, traverse_step_func=None, *args):
"""
While traversing in order, execute the provided function,
passing in each node's data as well as an arbitrary number
of provided arguments.
If no traverse_step_func is provided, an array of the traversal
will be returned.
"""
if traverse_step_func is None:
return self._traverse_default_wrapper(self.traverse_in_order)
self.left and self.left.traverse_in_order(traverse_step_func, *args)
traverse_step_func(self.data, *args)
self.right and self.right.traverse_in_order(traverse_step_func, *args)
def traverse_pre_order(self, traverse_step_func=None, *args):
if traverse_step_func is None:
return self._traverse_default_wrapper(self.traverse_pre_order)
traverse_step_func(self.data, *args)
self.left and self.left.traverse_pre_order(traverse_step_func, *args)
self.right and self.right.traverse_pre_order(traverse_step_func, *args)
def traverse_post_order(self, traverse_step_func=None, *args):
if traverse_step_func is None:
return self._traverse_default_wrapper(self.traverse_post_order)
self.left and self.left.traverse_post_order(traverse_step_func, *args)
self.right and self.right.traverse_post_order(
traverse_step_func, *args)
traverse_step_func(self.data, *args)
def traverse_level_order(self):
queue = Queue()
queue.enqueue(self)
arr = []
while(not queue.is_empty()):
current = queue.dequeue()
arr.append(current.data)
for child in [current.left, current.right]:
if(child):
queue.enqueue(child)
return arr