Last active
September 27, 2019 10:10
-
-
Save zeyu2001/c57f9d05db8ac69c9fdc0d110a85277b to your computer and use it in GitHub Desktop.
Binary Search Tree (BST) Dynamic Node Python Implementation
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
| # BST (OOP Array/FreeSlot Linked List Implementation) -----------# | |
| class Node: | |
| def __init__(self, data, ptr, leftPtr, rightPtr): | |
| self._data = data | |
| self._ptr = ptr | |
| self._leftPtr = leftPtr | |
| self._rightPtr = rightPtr | |
| def get_data(self): | |
| return self._data | |
| def get_ptr(self): | |
| return self._ptr | |
| def get_leftPtr(self): | |
| return self._leftPtr | |
| def get_rightPtr(self): | |
| return self._rightPtr | |
| def set_data(self, data): | |
| self._data = data | |
| def set_ptr(self, ptr): | |
| self._ptr = ptr | |
| def set_leftPtr(self, leftPtr): | |
| self._leftPtr = leftPtr | |
| def set_rightPtr(self, rightPtr): | |
| self._rightPtr = rightPtr | |
| def __str__(self): | |
| return "Data Value: " + self._data + " , Pointer Value: " + str(self._ptr) | |
| class BST: | |
| def __init__(self, size): | |
| self._tree = [Node('', i + 1, -1, -1) for i in range(size - 1)] | |
| self._tree.append(Node('', -1, -1, -1)) | |
| self._root = -1 | |
| self._nextFree = 0 | |
| def getFreeNode(self): | |
| if self._nextFree == -1: | |
| return 0 | |
| else: | |
| temp = self._nextFree | |
| self._nextFree = self._tree[temp].get_ptr() | |
| self._tree[temp].set_ptr(0) | |
| return temp | |
| def returnNode(self, ptr): | |
| # begin: add to nextFree linked list | |
| node = self._tree[ptr] | |
| node.set_ptr(self._nextFree) | |
| self._nextFree = ptr | |
| # end: add to nextFree linked list | |
| # begin: 'reset' node | |
| node.set_data('') | |
| node.set_leftPtr(-1) | |
| node.set_rightPtr(-1) | |
| # end: 'reset' node | |
| def addNode(self, newItem): | |
| if self._nextFree == -1: | |
| return | |
| else: | |
| # begin: set data to free node | |
| free_pos = self.getFreeNode() | |
| free_node = self._tree[free_pos] | |
| free_node.set_data(newItem) | |
| # end: set data to free node | |
| # begin: assign free node to correct branch of BST | |
| if self._root == -1: | |
| self._root = free_pos | |
| else: | |
| # begin: traverse the tree until the free position is found | |
| def helper(curr, data): | |
| curr_data = self._tree[curr].get_data() | |
| if data > curr_data: | |
| rightPtr = self._tree[curr].get_rightPtr() | |
| # found it | |
| if rightPtr == -1: | |
| self._tree[curr].set_rightPtr(free_pos) | |
| else: | |
| helper(rightPtr, data) | |
| else: | |
| leftPtr = self._tree[curr].get_leftPtr() | |
| # found it | |
| if leftPtr == -1: | |
| self._tree[curr].set_leftPtr(free_pos) | |
| else: | |
| helper(leftPtr, data) | |
| helper(self._root, newItem) | |
| # end: traverse the tree until the free position is found | |
| # end: assign free node to correct branch of BST | |
| def deleteRoot(self): | |
| if self._root == -1: | |
| return | |
| root_node = self._tree[self._root] | |
| # begin: simple cases | |
| if root_node.get_leftPtr() == -1 and root_node.get_rightPtr() == -1: | |
| self.returnNode(self._root) | |
| self._root = -1 | |
| elif root_node.get_leftPtr() == -1 and root_node.get_rightPtr() != -1: | |
| temp = self._root | |
| self._root = root_node.get_rightPtr() | |
| self.returnNode(temp) | |
| elif root_node.get_rightPtr() == -1 and root_node.get_leftPtr() != -1: | |
| temp = self._root | |
| self._root = root_node.get_leftPtr() | |
| self.returnNode(temp) | |
| # end: simple cases | |
| # begin: have both left and right child | |
| else: | |
| # begin: find maximum of left subtree (and its parent) | |
| def findMax(root, prev): | |
| if self._tree[root].get_rightPtr() == -1: | |
| return [root, prev] | |
| else: | |
| return findMax(self._tree[root].get_rightPtr(), root) | |
| [left_max, parent] = findMax(self._tree[self._root].get_leftPtr(), None) | |
| # end: find maximum of left subtree (and its parent) | |
| # begin: set root to be maximum of left subtree | |
| self._tree[left_max].set_rightPtr(root_node.get_rightPtr()) | |
| if parent: | |
| # successor is a right child | |
| # right child of parent <-- left child of successor | |
| self._tree[parent].set_rightPtr(self._tree[left_max].get_leftPtr()) | |
| # left child of successor <-- left child of root | |
| self._tree[left_max].set_leftPtr(root_node.get_leftPtr()) | |
| else: | |
| # successor is just the left child of root | |
| pass | |
| temp = self._root | |
| self._root = left_max | |
| # end: set root to be maximum of left subtree | |
| self.returnNode(temp) | |
| # end: have both left and right child | |
| def height(self): | |
| def helper(curr): | |
| if curr == -1: | |
| return -1 | |
| else: | |
| return max(1 + helper(self._tree[curr].get_leftPtr()),\ | |
| 1 + helper(self._tree[curr].get_rightPtr())) | |
| return helper(self._root) | |
| def childCount(self): | |
| # Returns the total number of nodes in the logical BST that has only 1 child. | |
| # If there is no node in the logical BST, it returns 0. | |
| def helper(curr): | |
| if self._root == -1: | |
| return 0 | |
| elif curr.get_leftPtr() == -1 and curr.get_rightPtr() != -1: | |
| return 1 | |
| elif curr.get_rightPtr() == -1 and curr.get_leftPtr() != -1: | |
| return 1 | |
| elif curr.get_leftPtr() != -1 and curr.get_rightPtr() != -1: | |
| return helper(self._tree[curr.get_leftPtr()]) + \ | |
| helper(self._tree[curr.get_rightPtr()]) | |
| else: | |
| return 0 | |
| return helper(self._tree[self._root]) | |
| def reverseTraversal(self): | |
| to_ret = [] | |
| def helper(curr): | |
| nonlocal to_ret | |
| # right (biggest) | |
| if curr.get_rightPtr() != -1: | |
| helper(self._tree[curr.get_rightPtr()]) | |
| # root | |
| to_ret.append(curr.get_data()) | |
| # left (smallest) | |
| if curr.get_leftPtr() != -1: | |
| helper(self._tree[curr.get_leftPtr()]) | |
| helper(self._tree[self._root]) | |
| return to_ret | |
| def inOrderTraversal(self): | |
| if self._root == -1: | |
| return [] | |
| to_ret = [] | |
| def helper(curr): | |
| nonlocal to_ret | |
| # left (smallest) | |
| if curr.get_leftPtr() != -1: | |
| helper(self._tree[curr.get_leftPtr()]) | |
| # root | |
| to_ret.append(curr.get_data()) | |
| # right (biggest) | |
| if curr.get_rightPtr() != -1: | |
| helper(self._tree[curr.get_rightPtr()]) | |
| helper(self._tree[self._root]) | |
| return to_ret | |
| def preOrderTraversal(self): | |
| to_ret = [] | |
| def helper(curr): | |
| nonlocal to_ret | |
| # root | |
| to_ret.append(curr.get_data()) | |
| # left | |
| if curr.get_leftPtr() != -1: | |
| helper(self._tree[curr.get_leftPtr()]) | |
| # right | |
| if curr.get_rightPtr() != -1: | |
| helper(self._tree[curr.get_rightPtr()]) | |
| helper(self._tree[self._root]) | |
| return to_ret | |
| def postOrderTraversal(self): | |
| to_ret = [] | |
| def helper(curr): | |
| nonlocal to_ret | |
| # left | |
| if curr.get_leftPtr() != -1: | |
| helper(self._tree[curr.get_leftPtr()]) | |
| # right | |
| if curr.get_rightPtr() != -1: | |
| helper(self._tree[curr.get_rightPtr()]) | |
| # root | |
| to_ret.append(curr.get_data()) | |
| helper(self._tree[self._root]) | |
| return to_ret | |
| def displayArray(self): | |
| print("next free", self._nextFree) | |
| print('root', self._root) | |
| for i in range(len(self._tree)): | |
| print ("Slot Number "+ str(i) + " " + str(self._tree[i]) + \ | |
| ' leftPtr: ' + str(self._tree[i]._leftPtr) + \ | |
| ' rightPtr: ' + str(self._tree[i]._rightPtr)) | |
| def test1(): | |
| BT = BST(7) | |
| BT.addNode("Dave") | |
| BT.addNode("Fred") | |
| BT.addNode("Ed") | |
| BT.addNode("Greg") | |
| BT.addNode("Bob") | |
| BT.addNode("Cid") | |
| BT.addNode("John") | |
| BT.addNode("Ali") #not added because it is the 8th node | |
| return BT.inOrderTraversal() == ['Bob', 'Cid', 'Dave', 'Ed', 'Fred', 'Greg', 'John'] and BT.height() == 3 | |
| def test2(): | |
| BT = BST(7) | |
| BT.addNode("Dave") | |
| BT.addNode("Fred") | |
| BT.addNode("Ed") | |
| BT.addNode("Greg") | |
| BT.addNode("Bob") | |
| BT.addNode("Cid") | |
| BT.addNode("Ali") | |
| #Call for deleteRoot 8 times | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| a = BT.height() # a = 0 because BST has only 1 node | |
| BT.deleteRoot() | |
| b = BT.height() # -1 No BST no height | |
| #BST is empty, deleteRoot() does nothing | |
| return BT.inOrderTraversal() == [] and a == 0 and b == -1 | |
| def test3(): | |
| BT = BST(7) | |
| BT.addNode("Dave") | |
| BT.addNode("Fred") | |
| BT.addNode("Ed") | |
| BT.addNode("Greg") | |
| BT.addNode("Bob") | |
| BT.addNode("Cid") | |
| BT.addNode("Ali") | |
| #Call for deleteRoot 8 times | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| BT.deleteRoot() | |
| #re-insert the items to ensure BST work again. | |
| BT.addNode("Dave") | |
| BT.addNode("Fred") | |
| BT.addNode("Ed") | |
| BT.addNode("Greg") | |
| BT.addNode("Bob") | |
| BT.addNode("Cid") | |
| BT.addNode("Ali") | |
| return BT.inOrderTraversal() == ['Ali', 'Bob', 'Cid', 'Dave', 'Ed', 'Fred', 'Greg'] | |
| print(test1()) | |
| print(test2()) | |
| print(test3()) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment