Created
January 29, 2013 04:10
-
-
Save TheDataLeek/4661723 to your computer and use it in GitHub Desktop.
First file is my test code, second is my actual python code.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env | |
# | |
# binary_search_tree.py | |
# | |
class bt_node: | |
data = 0 | |
left = None | |
right = None | |
class BinarySearchTree: | |
def __init__(self): | |
self.tree = None | |
self.tree_list = [] | |
def init_node(self, data): | |
""" | |
Create and return a bt_node object that has been initialized | |
with the given data and two None children. | |
""" | |
new_node = bt_node() | |
new_node.data = data | |
return new_node | |
def insert(self, new_node): | |
""" | |
Insert the new_node into the tree at the correct location. | |
""" | |
if self.tree is None: | |
self.tree = new_node | |
else: | |
cursor = self.tree | |
while True: | |
if new_node.data < cursor.data: | |
if cursor.left is None: | |
cursor.left = new_node | |
break | |
else: | |
cursor = cursor.left | |
if new_node.data >= cursor.data: | |
if cursor.right is None: | |
cursor.right = new_node | |
break | |
else: | |
cursor = cursor.right | |
def insert_data(self, data): | |
""" | |
Insert a new node that contains the given data into the tree | |
at the correct location. | |
""" | |
new_node = self.init_node(data) | |
self.insert(new_node) | |
def remove(self, data): | |
""" | |
Removes a node from the tree whose data value is the same as | |
the argument. | |
""" | |
if self.contains(data): | |
cursor = self.tree | |
prev = None | |
while True: | |
if data < cursor.data: | |
prev = cursor | |
cursor = cursor.left | |
if data >= cursor.data: | |
if cursor.data == data: | |
break | |
else: | |
prev = cursor | |
cursor = cursor.right | |
if cursor.left is None and cursor.right is None: | |
if prev.left == cursor: # Case one, no childs | |
prev.left = None | |
if prev.right == cursor: | |
prev.right = None | |
elif cursor.left is None and cursor.right is not None: | |
if prev.left == cursor: # Case two - right child | |
prev.left = cursor.right | |
if prev.right == cursor: | |
prev.left = cursor.right | |
elif cursor.right is None and cursor.left is not None: | |
if prev.left == cursor: # Case three - left child | |
prev.left = cursor.left | |
if prev.right == cursor: | |
prev.left = cursor.left | |
else: # Case four, two childs | |
successor_node = cursor.right | |
successor_top = None | |
while True: | |
if successor_node.left == None: | |
break | |
else: | |
successor_top = successor_node | |
successor_node = successor_node.left | |
cursor.data = successor_node.data | |
if successor_node.left != None: | |
successor_top.left = successor_node.left | |
if successor_node.right != None: | |
successor_top.right = successor_node.right | |
successor_node.left = None | |
successor_node.right = None | |
def contains(self, data): | |
""" | |
Return True or False depending on if this tree contains a node | |
with the supplied data. | |
""" | |
if self.tree is None: | |
return False | |
else: | |
cursor = self.tree | |
while True: | |
if data < cursor.data: | |
if cursor.data == data: | |
return True | |
if cursor.left is None: | |
return False | |
else: | |
cursor = cursor.left | |
if data >= cursor.data: | |
if cursor.data == data: | |
return True | |
if cursor.right is None: | |
return False | |
else: | |
cursor = cursor.right | |
def get_node(self, data): | |
""" | |
If the tree contains a node with the supplied data, return | |
it. Otherwise return None. | |
""" | |
if self.contains(data): | |
cursor = self.tree | |
while True: | |
if data < cursor.data: | |
cursor = cursor.left | |
if data >= cursor.data: | |
if cursor.data == data: | |
return cursor | |
else: | |
cursor = cursor.right | |
else: | |
return None | |
def size(self): | |
""" | |
Return the size of this tree. If it is empty this returns 0. | |
""" | |
if self.tree is None: | |
return 0 | |
else: | |
return len(self.to_array()) | |
def to_array(self): | |
""" | |
Create and fill a list with the data contained in this | |
tree. The elements of the returned list must be in the same | |
order as they are found during an inorder traversal, which | |
means the numbers should be in non-decreasing order. | |
""" | |
if self.tree is None: | |
return [] | |
else: | |
self.tree_list = [] | |
self.search(self.tree) | |
return self.tree_list | |
def search(self, node): | |
if node != None: | |
self.tree_list.append(node.data) | |
self.search(node.left) | |
self.search(node.right) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python | |
import unittest | |
from binary_search_tree import BinarySearchTree | |
class TestBinarySearchTree(unittest.TestCase): | |
def __init__(self, *args, **kwargs): | |
unittest.TestCase.__init__(self, *args, **kwargs) | |
def setUp(self): | |
self.bst = BinarySearchTree() | |
self.node_5 = self.bst.init_node(-5) | |
self.node_4 = self.bst.init_node(-4) | |
self.node_3 = self.bst.init_node(-3) | |
self.node_2 = self.bst.init_node(-2) | |
self.node_1 = self.bst.init_node(-1) | |
self.node0 = self.bst.init_node(0) | |
self.node1 = self.bst.init_node(1) | |
self.node2 = self.bst.init_node(2) | |
self.node3 = self.bst.init_node(3) | |
self.node4 = self.bst.init_node(4) | |
self.node5 = self.bst.init_node(5) | |
self.mytree = BinarySearchTree() | |
self.mytree.insert_data(5) | |
self.mytree.insert_data(2) | |
self.mytree.insert_data(3) | |
self.mytree.insert_data(1) | |
self.mytree.insert_data(4) | |
self.mytree.insert_data(0) | |
self.mytree.insert_data(2.5) | |
self.mytree.insert_data(8) | |
self.mytree.insert_data(9) | |
self.mytree.insert_data(6) | |
self.mytree.insert_data(4.5) | |
def test_init_node(self): | |
node1 = self.bst.init_node(5) | |
node2 = self.bst.init_node(4) | |
assert(node1.data == 5) | |
assert(node1.left == None) | |
assert(node1.right == None) | |
assert(node2.data == 4) | |
assert(node2.left == None) | |
assert(node2.right == None) | |
def test_insert(self): | |
assert(self.bst.tree == None) | |
self.bst.insert(self.node0) | |
assert(self.bst.tree.data == self.node0.data) | |
self.bst.insert(self.node3) | |
assert(self.bst.tree.right.data == self.node3.data) | |
self.bst.insert(self.node5) | |
assert(self.bst.tree.right.right.data == self.node5.data) | |
self.bst.insert(self.node4) | |
assert(self.bst.tree.right.right.left.data == self.node4.data) | |
self.bst.insert(self.node2) | |
assert(self.bst.tree.right.left.data == self.node2.data) | |
self.bst.insert(self.node1) | |
assert(self.bst.tree.right.left.left.data == self.node1.data) | |
self.bst.insert(self.node_4) | |
assert(self.bst.tree.left.data == self.node_4.data) | |
self.bst.insert(self.node_5) | |
assert(self.bst.tree.left.left.data == self.node_5.data) | |
self.bst.insert(self.node_2) | |
assert(self.bst.tree.left.right.data == self.node_2.data) | |
self.bst.insert(self.node_3) | |
assert(self.bst.tree.left.right.left.data == self.node_3.data) | |
self.bst.insert(self.node_1) | |
assert(self.bst.tree.left.right.right.data == self.node_1.data) | |
def test_remove(self): | |
assert(self.mytree.contains(0) == True) | |
self.mytree.remove(0) | |
assert(self.mytree.contains(0) == False) | |
assert(self.mytree.contains(4.5) == True) | |
self.mytree.remove(4.5) | |
assert(self.mytree.contains(4.5) == False) | |
self.mytree.insert_data(0) | |
assert(self.mytree.contains(1) == True) | |
self.mytree.remove(1) | |
assert(self.mytree.contains(1) == False) | |
assert(self.mytree.contains(0) == True) | |
assert(self.mytree.contains(2) == True) | |
self.mytree.remove(2) | |
assert(self.mytree.contains(2) == False) | |
assert(self.mytree.contains(0) == True) | |
assert(self.mytree.contains(3) == True) | |
assert(self.mytree.contains(2.5) == True) | |
assert(self.mytree.contains(4) == True) | |
def test_contains(self): | |
assert(self.mytree.contains(5) == True) | |
assert(self.mytree.contains(4) == True) | |
assert(self.mytree.contains(3) == True) | |
assert(self.mytree.contains(2) == True) | |
assert(self.mytree.contains(1) == True) | |
assert(self.mytree.contains(0) == True) | |
assert(self.mytree.contains(9) == True) | |
assert(self.mytree.contains(80) == False) | |
assert(self.mytree.contains(-5) == False) | |
assert(self.mytree.contains(-10) == False) | |
assert(self.mytree.contains(230) == False) | |
assert(self.mytree.contains(340) == False) | |
def test_get_node(self): | |
acquired_node0 = self.mytree.get_node(2) | |
acquired_node1 = self.mytree.get_node(8) | |
acquired_node2 = self.mytree.get_node(4.5) | |
acquired_node3 = self.mytree.get_node(45) | |
assert(acquired_node0.data == 2) | |
assert(acquired_node0.left.data == 1) | |
assert(acquired_node0.right.data == 3) | |
assert(acquired_node1.data == 8) | |
assert(acquired_node1.left.data == 6) | |
assert(acquired_node1.right.data == 9) | |
assert(acquired_node2.data == 4.5) | |
assert(acquired_node2.left == None) | |
assert(acquired_node2.right == None) | |
assert(acquired_node3 == None) | |
def test_to_array(self): | |
assert(self.bst.to_array() == []) | |
self.bst.insert_data(5) | |
self.bst.insert_data(2) | |
self.bst.insert_data(8) | |
self.bst.insert_data(6) | |
self.bst.insert_data(1) | |
self.bst.insert_data(3) | |
self.bst.insert_data(0) | |
self.bst.insert_data(4) | |
self.bst.insert_data(9) | |
assert(self.bst.to_array() == [5, 2, 1, 0, 3, 4, 8, 6, 9]) | |
assert(self.mytree.to_array() == [5, 2, 1, 0, 3, 2.5, 4, 4.5, 8, 6, 9]) | |
def test_size(self): | |
assert(self.mytree.size() == 11) | |
self.mytree.remove(4.5) | |
assert(self.mytree.size() == 10) | |
self.mytree.remove(4) | |
assert(self.mytree.size() == 9) | |
self.mytree.insert_data(30) | |
assert(self.mytree.size() == 10) | |
if __name__ == "__main__": | |
unittest.main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
zomg awesome. this will save some time today. +3