Advertisement
david929

aaaa

Jul 5th, 2022
792
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.38 KB | None
  1. # Your implementation goes here
  2.  
  3. class BinarySearchTree:
  4.     # This is a Node class that is internal to the BinarySearchTree class
  5.     class __Node:
  6.         def __init__(self, val, left=None, right=None):
  7.             self.val = val
  8.             self.left = left
  9.             self.right = right
  10.            
  11.         def getVal(self):
  12.             return self.val
  13.  
  14.         def setVal(self, newval):
  15.             self.val = newval
  16.            
  17.         def getLeft(self):
  18.             return self.left
  19.        
  20.         def getRight(self):
  21.             return self.right
  22.        
  23.         def setLeft(self, newleft):
  24.             self.left = newleft
  25.        
  26.         def setRight(self, newright):
  27.             self.right = newright
  28.            
  29.         # This method deserves a little explanation. It does an inorder traversal
  30.         # of the nodes of the tree yielding all the values. In this way, we get
  31.         # the values in ascending order.      
  32.         def __iter__(self):
  33.             if self.left != None:
  34.                 for elem in self.left:
  35.                     yield elem
  36.             yield self.val
  37.             if self.right != None:
  38.                 for elem in self.right:
  39.                     yield elem
  40.                    
  41.     # Below methods of the BinarySearchTree class.
  42.     def __init__(self):
  43.         self.root = None
  44.          
  45.     def insert(self, val):  
  46.         # The __insert function is recursive and is not a passed a self parameter.
  47.         # It is a # static function (not a method of the class) but is hidden inside the insert
  48.         # function so users of the class will not know it exists.
  49.         def __insert(root, val):
  50.             if root == None:
  51.                 return BinarySearchTree.__Node(val)
  52.             if val < root.getVal():
  53.                 root.setLeft( __insert(root.getLeft(), val) )
  54.             else:
  55.                 root.setRight(__insert(root.getRight(), val))
  56.             return root
  57.        
  58.         self.root = __insert(self.root, val)
  59.        
  60.     def search(self, val):
  61.         def __search(root,val):
  62.             if root == None:
  63.                 return False
  64.             if root.getVal() == val:
  65.                 return True
  66.             if val < root.getVal():
  67.                 return __search(root.getLeft(), val)
  68.             return __search(root.getRight(), val)
  69.        
  70.         return __search(self.root,val)
Advertisement
RAW Paste Data Copied
Advertisement