Created
February 7, 2019 23:54
-
-
Save Rui-qi-Li/2a6af7f7450049d31b2893d8e16d58a5 to your computer and use it in GitHub Desktop.
create Binary Search Tree in Python including Node class and BST class
This file contains hidden or 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
| class Node: | |
| def __init__(self,data): | |
| self.data = data | |
| self.left = None | |
| self.right = None | |
| def getChildren(self): | |
| children=[] | |
| if self.left: | |
| children.append(self.left) | |
| if self.right: | |
| children.append(self.right) | |
| return children | |
| class BST: | |
| def __init__(self,data): | |
| self.root = Node(data) | |
| def insert(self,data): | |
| if not self.root: | |
| self.root =Node(data) | |
| else: | |
| self.insertNode(self.root,data) | |
| def insertNode(self,curr,data): | |
| if data<=curr.data: | |
| if curr.left: | |
| self.insertNode(curr.left,data) | |
| else: | |
| curr.left = Node(data) | |
| else: | |
| if curr.right: | |
| self.insertNode(curr.right,data) | |
| else: | |
| curr.right = Node(data) | |
| def find(self,data): | |
| return self.findNode(self.root,data) | |
| def findNode(self,curr,data): | |
| if not curr: | |
| return False | |
| elif data == curr.data: | |
| return True | |
| elif data < curr.data: | |
| return self.findNode(curr.left,data) | |
| elif data > curr.data: | |
| return self.findNode(curr.right,data) | |
| def inorder(self): | |
| if not self.root: | |
| return 'Empty tree' | |
| else: | |
| self.inorderNode(self.root) | |
| def inorderNode(self,curr): | |
| if curr.left: # print left | |
| self.inorderNode(curr.left) | |
| print(curr.data) # print root | |
| if curr.right: | |
| self.inorderNode(curr.right) # print right | |
| def preorder(self): | |
| if not self.root: | |
| return 'Empty tree' | |
| else: | |
| self.preorderNode(self.root) | |
| def preorderNode(self,curr): | |
| print(curr.data) # print root | |
| if curr.left: # print left | |
| self.preorderNode(curr.left) | |
| if curr.right: # print left | |
| self.preorderNode(curr.right) | |
| def minvalue(self): | |
| if not self.root: | |
| return 'Empty tree' | |
| else: | |
| minNode = self.minvalueNode(self.root) | |
| print(minNode.data) | |
| def minvalueNode(self,curr): | |
| while curr.left: | |
| curr = curr.left | |
| return curr | |
| def delete(self,data): | |
| if not self.root: | |
| return 'Empty tree, del reject' | |
| else: | |
| self.deleteNode(self.root,data) | |
| def deleteNode(self,curr,data): | |
| # base case | |
| if not curr: | |
| return curr # None | |
| if data < curr.data: | |
| curr.left = self.deleteNode(curr.left,data) | |
| elif data > curr.data: | |
| curr.right = self.deleteNode(curr.right,data) | |
| else: # found node need to be deleted | |
| # 0/1 right child | |
| if not curr.left: | |
| temp = curr.right | |
| curr = None | |
| return temp | |
| elif not curr.left: | |
| temp = curr.left | |
| curr = None | |
| return temp | |
| # 2 children | |
| # get the inorder successor (smallest in the right subtree) | |
| temp = self.minvalueNode(curr.right) | |
| # copy the inorder successor's content to this Node | |
| curr.data = temp.data | |
| # delete the inorder successor, single leaf | |
| self.deleteNode(curr.right, temp.data) | |
| return curr # return curr/curr.left/curr.right |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment