Skip to content

Commit c840bab

Browse files
laurentlucelaurentluce
committed
Node class only
1 parent e6e9384 commit c840bab

File tree

4 files changed

+709
-189
lines changed

4 files changed

+709
-189
lines changed

‎algorithms/binary_tree.py

+141-170
Original file line numberDiff line numberDiff line change
@@ -12,191 +12,162 @@ def __init__(self, data):
1212
self.right = None
1313
self.data = data
1414

15-
class BinaryTree:
16-
"""
17-
Binary tree: methods to manipulate a binary tree
18-
"""
19-
def __init__(self):
20-
"""
21-
Binary tree constructor
15+
def insert(self, data):
2216
"""
23-
self.root = None
17+
Insert new node with data
2418
25-
def get_root(self):
26-
return self.root
19+
@param data node data object to insert
20+
"""
21+
elif data < self.data:
22+
if self.left == None:
23+
self.left = Node(data)
24+
else:
25+
self.left.insert(data)
26+
else:
27+
if self.right == None:
28+
self.right = Node(data)
29+
else:
30+
self.right.insert(data)
2731

28-
def insert(self, data):
29-
node = bt_insert(self.root, data)
30-
if self.root == None:
31-
self.root = node
32+
def lookup(self, data, parent=None):
33+
"""
34+
Lookup node containing data
3235
33-
def lookup(self, data):
34-
return bt_lookup(self.root, data)
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 == None:
42+
return None, None
43+
return self.left.lookup(data, self)
44+
elif data > self.data:
45+
if self.right == None:
46+
return None, None
47+
return self.right.lookup(data, self)
48+
else:
49+
return self, parent
3550

3651
def delete(self, data):
37-
return bt_delete(self.root, data)
52+
"""
53+
Delete node containing data
3854
39-
def compare_trees(self, root):
40-
return bt_compare_trees(self.root, root)
55+
@param data node's content to delete
56+
"""
57+
# get node containing data
58+
node, parent = self.lookup(data)
59+
if node != None:
60+
children_count = self.children_count(node)
61+
if children_count == 0:
62+
# if node has no children, just remove it
63+
if self.which_child(parent, node) == 'left':
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
89+
else:
90+
parent.right = successor.right
91+
92+
def compare_trees(self, node):
93+
"""
94+
Compare 2 trees
4195
96+
@param node tree to compare
97+
@returns True if the tree passed is identical to this tree
98+
"""
99+
if node == None:
100+
return False
101+
if self.data != node.data:
102+
return False
103+
res = True
104+
if self.left == None:
105+
if node.left:
106+
return False
107+
else:
108+
res = self.left.compare_trees(node.left)
109+
if self.right == None:
110+
if node.right:
111+
return False
112+
else:
113+
res = self.right.compare_trees(node.right)
114+
return res
115+
42116
def print_tree(self):
43-
bt_print_tree(self.root)
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()
44125

45126
def tree_data(self):
46-
return bt_tree_data(self.root)
47-
48-
def bt_insert(root, data):
49-
"""
50-
Insert new node with data
51-
52-
@param root tree root
53-
@param data node data object
54-
@returns inserted node
55-
"""
56-
if root == None:
57-
root = Node(data)
58-
else:
59-
if data <= root.data:
60-
root.left = bt_insert(root.left, data)
61-
else:
62-
root.right = bt_insert(root.right, data)
63-
return root
64-
65-
def bt_lookup(root, data, parent=None):
66-
"""
67-
Lookup node containing data
68-
69-
@param root tree root
70-
@param data node data object
71-
@returns node and node's parent if found or None, None
72-
"""
73-
if root == None:
74-
return None, None
75-
if data < root.data:
76-
return bt_lookup(root.left, data, root)
77-
elif data > root.data:
78-
return bt_lookup(root.right, data, root)
79-
else:
80-
return root, parent
81-
82-
def bt_compare_trees(root1, root2):
83-
"""
84-
Compare 2 trees
85-
86-
@param root1 tree 1 root node
87-
@param root2 tree 2 root node
88-
@returns True if the 2 trees are identical or False
89-
"""
90-
if root1 == None and root2 == None:
91-
return True
92-
elif (root1 == None and root2 != None) or (root1 != None and root2 == None):
93-
return False
94-
else:
95-
return (root1.data == root2.data) \
96-
and bt_compare_trees(root1.left, root2.left) \
97-
and bt_compare_trees(root1.right, root2.right)
98-
99-
def bt_print_tree(root):
100-
"""
101-
Print tree content inorder
102-
103-
@param root tree root node
104-
"""
105-
if root:
106-
bt_print_tree(root.left)
107-
print root.data,
108-
bt_print_tree(root.right)
109-
110-
def bt_tree_data(root):
111-
"""
112-
Generator to get the tree nodes data
113-
114-
@param node tree root node
115-
"""
116-
# we use a stack to traverse the tree in a non-recursive way
117-
stack = []
118-
node = root
119-
while stack or node:
120-
if node:
121-
stack.append(node)
122-
node = node.left
123-
else: # we are returning so we pop the node and we yield it
124-
node = stack.pop()
125-
yield node.data
126-
node = node.right
127-
128-
def bt_delete(root, data):
129-
"""
130-
Delete node containing data
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
141+
142+
def which_child(self, parent, child):
143+
"""
144+
Test if child is parent's left child or parent's right child
131145
132-
@param root tree root node
133-
@param data node's content to delete
134-
"""
135-
# get node containing data
136-
node, parent = bt_lookup(root, data)
137-
if node != None:
138-
children_count = bt_children_count(node)
139-
if children_count == 0:
140-
# if node has no children, just remove it
141-
if bt_which_child(parent, node) == 'left':
142-
parent.left = None
143-
else:
144-
parent.right = None
145-
elif children_count == 1:
146-
# if node has 1 child
147-
# replace node by its child
148-
if node.left:
149-
node.data = node.left.data
150-
node.left = None
151-
else:
152-
node.data = node.right.data
153-
node.right = None
146+
@param parent parent node
147+
@param child parent's child node
148+
"""
149+
if parent == None:
150+
return None
151+
if parent.left == child:
152+
return 'left'
154153
else:
155-
# if node has 2 children
156-
# find its successor
157-
parent = node
158-
successor = node.right
159-
while successor.left:
160-
parent = successor
161-
successor = successor.left
162-
node.data = successor.data
163-
# if the successor has a child, replace it with its child
164-
# it can only be a right child at this point
165-
if successor.right:
166-
successor.data = successor.right.data
167-
successor.right = None
168-
else:
169-
parent.left = None
154+
return 'right'
170155

171-
def bt_which_child(parent, child):
172-
"""
173-
Test if child is parent's left child or parent's right child
174-
175-
@param parent parent node
176-
@param child parent's child node
177-
"""
178-
if parent == None:
179-
return None
180-
if parent.left == child:
181-
return 'left'
182-
else:
183-
return 'right'
184-
185-
def bt_children_count(node):
186-
"""
187-
Return the number of children
156+
def children_count(self, node):
157+
"""
158+
Return the number of children
188159
189-
@param node node to get nb of children
190-
@returns number of children: 0, 1, 2
191-
"""
192-
if node == None:
193-
return None
194-
cnt = 0
195-
if node.left:
196-
cnt += 1
197-
if node.right:
198-
cnt += 1
199-
return cnt
160+
@param node node to get nb of children
161+
@returns number of children: 0, 1, 2
162+
"""
163+
if node == None:
164+
return None
165+
cnt = 0
166+
if node.left:
167+
cnt += 1
168+
if node.right:
169+
cnt += 1
170+
return cnt
200171

201172

202173

‎algorithms/string_matching.py

100755100644
File mode changed.

0 commit comments

Comments
 (0)