Rui-qi-Li · February 7, 2019 23:54 · Feb 7, 2019
diff --git a/BST.py b/BST.py
@@ -0,0 +1,108 @@
+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
No results found