document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. # program to implement simple binary search tree in python
  2.  
  3. class node:
  4.    
  5.     # constructor method
  6.     # setting default value of left and right links to null
  7.     def __init__(self,element,left = None,right = None):
  8.         self.element = element
  9.         self.left = left
  10.         self.right = right
  11.  
  12.  
  13.     # method to update left Link   
  14.     def updateLeftLink(self,link):
  15.         self.left = link
  16.  
  17.  
  18.     # method to update right link  
  19.     def updateRightLink(self,link):
  20.         self.right = link  
  21.  
  22.  
  23.     # method to get the data element of the node
  24.     def getElement(self):
  25.         return self.element
  26.  
  27.     # method to get the Left node  
  28.     def getLeftNode(self):
  29.         return self.left
  30.    
  31.     # method to get the right node
  32.     def getRightNode(self):
  33.         return self.right  
  34.  
  35.  
  36. class BST:
  37.     def __init__(self):
  38.         self.root = None
  39.         self.pHeight = 0
  40.    
  41.    
  42.     # method returns true if the bst is empty
  43.     def isEmpty(self):
  44.         return self.root is None
  45.  
  46.     # method returns root of the binary search tree
  47.     def getRoot(self):
  48.         return self.root
  49.    
  50.    
  51.     # method inserts element in the binary search tree 
  52.     def insert(self,element):
  53.         tempNode = node(element)
  54.        
  55.         if self.getRoot() is None:
  56.             self.root = tempNode
  57.         else:
  58.             inserted = False
  59.             p = self.root
  60.             while not inserted:
  61.                 # if new element is greater the current element then insert it to the right
  62.                 if tempNode.getElement() > p.getElement():
  63.                     # if right link of the current is null then directly insert
  64.                     if p.getRightNode() is None:
  65.                         p.updateRightLink(tempNode)
  66.                         inserted = True
  67.                     else:
  68.                         p = p.getRightNode()
  69.                
  70.                 # if new element is less the current element then insert it to the left
  71.                 elif tempNode.getElement() < p.getElement():
  72.                     # if left link of the current is null then directly insert
  73.                     if p.getLeftNode() is None:
  74.                         p.updateLeftLink(tempNode)
  75.                         inserted = True
  76.                     else:
  77.                         p = p.getLeftNode()
  78.                
  79.    
  80.     # recursive method to display the binary tree in inorder
  81.     def displayInorder(self,tempNode):
  82.         if tempNode is None:
  83.             return
  84.         else:
  85.             self.displayInorder(tempNode.getLeftNode())
  86.             print(tempNode.getElement(), end="  ")
  87.             self.displayInorder(tempNode.getRightNode())
  88.  
  89.    
  90.     # recursive method to display the binary tree in preorder
  91.     def displayPreorder(self,tempNode):
  92.         if tempNode is None:
  93.             return
  94.         else:
  95.             print(tempNode.getElement(), end="  ")
  96.             self.displayPreorder(tempNode.getLeftNode())
  97.             self.displayPreorder(tempNode.getRightNode())
  98.  
  99.  
  100.     # recursive method to display binary tree in postorder     
  101.     def displayPostorder(self,tempNode):
  102.         if tempNode is None:
  103.             return
  104.         else:
  105.             self.displayPostorder(tempNode.getLeftNode())
  106.             self.displayPostorder(tempNode.getRightNode())
  107.             print(tempNode.getElement(), end="  ")
  108.    
  109.  
  110.     # method to search an element in the binary search tree
  111.     # if found method returns true
  112.     def search(self, element):
  113.    
  114.         # if the bst is empty return false
  115.         if self.isEmpty():
  116.             return False
  117.            
  118.         tempNode = self.getRoot()
  119.         found = False
  120.        
  121.         while not found:
  122.            
  123.             # if tempNode is null then the element is not present
  124.             # break out of the loop
  125.             if tempNode is None:
  126.                 break
  127.            
  128.             # if the element are less than current data traverse right
  129.             if tempNode.getElement() > element:
  130.                 tempNode = tempNode.getLeftNode()
  131.                
  132.             # if the element are greater than current data traverse left
  133.             elif tempNode.getElement() < element:
  134.                 tempNode = tempNode.getRightNode()
  135.                
  136.             # if the element is equal to the current data then set found to true   
  137.             elif tempNode.getElement() == element:
  138.                 found = True
  139.                
  140.         return found
  141.  
  142.  
  143. # main function
  144.  
  145. b1 = BST()
  146. b1.insert(7)
  147. b1.insert(29)
  148. b1.insert(25)
  149. b1.insert(36)
  150. b1.insert(71)
  151. b1.insert(24)
  152. b1.insert(5)
  153. b1.insert(9)
  154. b1.insert(1)
  155. root = b1.getRoot()
  156.  
  157. print("\\n\\nThe Inorder traversal of the BST is : ", end=" ")
  158. b1.displayInorder(root)
  159.  
  160. print("\\n\\nThe Preorder traversal of the BST is : ", end=" ")
  161. b1.displayPreorder(root)
  162.  
  163. print("\\n\\nThe Postorder traversal of the BST is : ", end=" ")
  164. b1.displayPostorder(root)
  165.  
  166. print("\\n")
  167. # searching for the elements in the binary search tree
  168. print(b1.search(25))
  169. print(b1.search(37))
  170.  
  171.  
  172. \'\'\'
  173.  
  174. The Inorder traversal of the BST is :  1  5  7  9  24  25  29  36  71
  175.  
  176. The Preorder traversal of the BST is :  7  5  1  29  25  24  9  36  71
  177.  
  178. The Postorder traversal of the BST is :  1  5  9  24  25  71  36  29  7
  179.  
  180. True
  181. False
  182.  
  183. \'\'\'
');