Skip to content

Commit f08f979

Browse files
laurentlucelaurentluce
committed
sync post with code
1 parent ef1148a commit f08f979

File tree

2 files changed

+152
-233
lines changed

2 files changed

+152
-233
lines changed

‎algorithms/binary_tree.py

+143-140
Original file line numberDiff line numberDiff line change
@@ -1,156 +1,159 @@
11
class Node:
2-
"""
3-
Tree node: left and right child + data which can be any object
4-
"""
5-
def __init__(self, data):
62
"""
7-
Node constructor
8-
9-
@param data node data object
10-
"""
11-
self.left = None
12-
self.right = None
13-
self.data = data
14-
15-
def insert(self, data):
3+
Tree node: left and right child + data which can be any object
164
"""
17-
Insert new node with data
5+
def __init__(self, data):
6+
"""
7+
Node constructor
188
19-
@param data node data object to insert
20-
"""
21-
if data < self.data:
22-
if self.left is None:
23-
self.left = Node(data)
24-
else:
25-
self.left.insert(data)
26-
else:
27-
if self.right is None:
28-
self.right = Node(data)
29-
else:
30-
self.right.insert(data)
9+
@param data node data object
10+
"""
11+
self.left = None
12+
self.right = None
13+
self.data = data
3114

32-
def lookup(self, data, parent=None):
33-
"""
34-
Lookup node containing data
15+
def insert(self, data):
16+
"""
17+
Insert new node with data
3518
36-
@param data node data object to look up
37-
@param parent node's parent
38-
@returns node and node's parent if found or None, None
39-
"""
40-
if data < self.data:
41-
if self.left is None:
42-
return None, None
43-
return self.left.lookup(data, self)
44-
elif data > self.data:
45-
if self.right is None:
46-
return None, None
47-
return self.right.lookup(data, self)
48-
else:
49-
return self, parent
19+
@param data node data object to insert
20+
"""
21+
if data < self.data:
22+
if self.left is None:
23+
self.left = Node(data)
24+
else:
25+
self.left.insert(data)
26+
else:
27+
if self.right is None:
28+
self.right = Node(data)
29+
else:
30+
self.right.insert(data)
5031

51-
def delete(self, data):
52-
"""
53-
Delete node containing data
32+
def lookup(self, data, parent=None):
33+
"""
34+
Lookup node containing data
5435
55-
@param data node's content to delete
56-
"""
57-
# get node containing data
58-
node, parent = self.lookup(data)
59-
if node is not None:
60-
children_count = node.children_count()
61-
if children_count == 0:
62-
# if node has no children, just remove it
63-
if parent.left is node:
64-
parent.left = None
65-
else:
66-
parent.right = None
67-
elif children_count == 1:
68-
# if node has 1 child
69-
# replace node by its child
70-
if node.left:
71-
node.data = node.left.data
72-
node.left = None
73-
else:
74-
node.data = node.right.data
75-
node.right = None
76-
else:
77-
# if node has 2 children
78-
# find its successor
79-
parent = node
80-
successor = node.right
81-
while successor.left:
82-
parent = successor
83-
successor = successor.left
84-
# replace node data by its successor data
85-
node.data = successor.data
86-
# fix successor's parent node child
87-
if parent.left == successor:
88-
parent.left = successor.right
36+
@param data node data object to look up
37+
@param parent node's parent
38+
@returns node and node's parent if found or None, None
39+
"""
40+
if data < self.data:
41+
if self.left is None:
42+
return None, None
43+
return self.left.lookup(data, self)
44+
elif data > self.data:
45+
if self.right is None:
46+
return None, None
47+
return self.right.lookup(data, self)
8948
else:
90-
parent.right = successor.right
49+
return self, parent
9150

92-
def compare_trees(self, node):
93-
"""
94-
Compare 2 trees
51+
def delete(self, data):
52+
"""
53+
Delete node containing data
9554
96-
@param node tree to compare
97-
@returns True if the tree passed is identical to this tree
98-
"""
99-
if node is None:
100-
return False
101-
if self.data != node.data:
102-
return False
103-
res = True
104-
if self.left is None:
105-
if node.left:
106-
return False
107-
else:
108-
res = self.left.compare_trees(node.left)
109-
if self.right is None:
110-
if node.right:
111-
return False
112-
else:
113-
res = self.right.compare_trees(node.right)
114-
return res
115-
116-
def print_tree(self):
117-
"""
118-
Print tree content inorder
119-
"""
120-
if self.left:
121-
self.left.print_tree()
122-
print self.data,
123-
if self.right:
124-
self.right.print_tree()
55+
@param data node's content to delete
56+
"""
57+
# get node containing data
58+
node, parent = self.lookup(data)
59+
if node is not None:
60+
children_count = node.children_count()
61+
if children_count == 0:
62+
# if node has no children, just remove it
63+
# check if it is not the root node
64+
if parent:
65+
if parent.left is node:
66+
parent.left = None
67+
else:
68+
parent.right = None
69+
del node
70+
elif children_count == 1:
71+
# if node has 1 child
72+
# replace node by its child
73+
if node.left:
74+
n = node.left
75+
else:
76+
n = node.right
77+
if parent.left is node:
78+
parent.left = n
79+
else:
80+
parent.right = n
81+
del node
82+
else:
83+
# if node has 2 children
84+
# find its successor
85+
parent = node
86+
successor = node.right
87+
while successor.left:
88+
parent = successor
89+
successor = successor.left
90+
# replace node data by its successor data
91+
node.data = successor.data
92+
# fix successor's parent node child
93+
if parent.left == successor:
94+
parent.left = successor.right
95+
else:
96+
parent.right = successor.right
12597

126-
def tree_data(self):
127-
"""
128-
Generator to get the tree nodes data
129-
"""
130-
# we use a stack to traverse the tree in a non-recursive way
131-
stack = []
132-
node = self
133-
while stack or node:
134-
if node:
135-
stack.append(node)
136-
node = node.left
137-
else: # we are returning so we pop the node and we yield it
138-
node = stack.pop()
139-
yield node.data
140-
node = node.right
98+
def compare_trees(self, node):
99+
"""
100+
Compare 2 trees
141101
142-
def children_count(self):
143-
"""
144-
Return the number of children
145-
146-
@returns number of children: 0, 1, 2
147-
"""
148-
cnt = 0
149-
if self.left:
150-
cnt += 1
151-
if self.right:
152-
cnt += 1
153-
return cnt
102+
@param node tree to compare
103+
@returns True if the tree passed is identical to this tree
104+
"""
105+
if node is None:
106+
return False
107+
if self.data != node.data:
108+
return False
109+
res = True
110+
if self.left is None:
111+
if node.left:
112+
return False
113+
else:
114+
res = self.left.compare_trees(node.left)
115+
if self.right is None:
116+
if node.right:
117+
return False
118+
else:
119+
res = self.right.compare_trees(node.right)
120+
return res
121+
122+
def print_tree(self):
123+
"""
124+
Print tree content inorder
125+
"""
126+
if self.left:
127+
self.left.print_tree()
128+
print self.data,
129+
if self.right:
130+
self.right.print_tree()
154131

132+
def tree_data(self):
133+
"""
134+
Generator to get the tree nodes data
135+
"""
136+
# we use a stack to traverse the tree in a non-recursive way
137+
stack = []
138+
node = self
139+
while stack or node:
140+
if node:
141+
stack.append(node)
142+
node = node.left
143+
else: # we are returning so we pop the node and we yield it
144+
node = stack.pop()
145+
yield node.data
146+
node = node.right
155147

148+
def children_count(self):
149+
"""
150+
Return the number of children
156151
152+
@returns number of children: 0, 1, 2
153+
"""
154+
cnt = 0
155+
if self.left:
156+
cnt += 1
157+
if self.right:
158+
cnt += 1
159+
return cnt

0 commit comments

Comments
 (0)