API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2014
175
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.94 KB | None | 0 0
raw download clone embed print report
  1. Q1.
  2. 81 99 154 232
  3.  
  4. Q2.
  5. 51 45 72 81 90 88 121 106 232 303 167
  6.  
  7. Q3.
  8. # Binary Search Tree
  9.  
  10. class BST:
  11. """A Binary Search Tree (BST) class."""
  12.  
  13. def __init__(self, value, parent=None):
  14. """Construct a BST.
  15.  
  16. value -- the value of the root node
  17. parent -- the parent node (of this BST subtree)
  18. """
  19. self.value = value
  20. self.left = None
  21. self.right = None
  22. self.parent = parent
  23.  
  24. def insert(self, value):
  25. """Insert value into the BST."""
  26. if value == self.value: # already in the tree
  27. return
  28. elif value < self.value:
  29. if self.left: # if it is not None
  30. self.left.insert(value)
  31. else:
  32. self.left = BST(value, parent=self) # create a new node
  33. else:
  34. if self.right:
  35. self.right.insert(value)
  36. else:
  37. self.right = BST(value, parent=self) # create a new node
  38.  
  39. def locate(self, value):
  40. """Return the node holding value."""
  41. if value == self.value:
  42. return self
  43. elif value < self.value and self.left:
  44. left_bst = self.left
  45. return left_bst.locate(value)
  46. elif value > self.value and self.right:
  47. right_bst = self.right
  48. return right_bst.locate(value)
  49. else:
  50. return None
  51.  
  52. def delete(self, value):
  53. """Delete value from the BST."""
  54. node = self.locate(value)
  55.  
  56. if node:
  57. left = node.left
  58. right = node.right
  59. if left and right: # both nodes are not None, i.e., two children
  60. node.delete_with_children()
  61. elif left or right: # one child
  62. node.delete_with_child()
  63. else: # no children
  64. node.delete_no_children()
  65.  
  66. def delete_no_children(self):
  67. if self.parent: #if parent exists
  68. if self.parent.left == self: #if is a left child
  69. self.parent.left = None
  70. else:
  71. self.parent.right = None
  72. else: # special case the root node
  73. self.value = None
  74.  
  75. def delete_with_child(self):
  76. if self.left:
  77. child = self.left
  78. else:
  79. child = self.right
  80. if self.parent:
  81. if self.parent.left == self:
  82. self.parent.left = child
  83. else:
  84. self.parent.right = child
  85. child.parent = self.parent
  86. else: # special case the root node
  87. self.replace(child)
  88.  
  89. def delete_with_children(self):
  90. replacement = self.right.min() # the successor
  91. successor_value = replacement.value
  92. self.delete(successor_value) # max of one child of this
  93. self.value = successor_value
  94.  
  95. def replace(self, other):
  96. """Replace this node with the values from other.
  97.  
  98. Also need to reattach other's children.
  99. """
  100. self.value = other.value
  101. self.left = other.left
  102. if self.left: self.left.parent = self
  103. self.right = other.right
  104. if self.right: self.right.parent = self
  105.  
  106. def min(self):
  107. """Returns the left most node of the BST."""
  108. min_node = self
  109. while min_node.left:
  110. min_node = min_node.left
  111. return min_node
  112. #------------------------------------------------------
  113. #------------------------------------------------------
  114. #Get the preorder string for the binary search tree
  115. #Get the postorder string for the binary search tree
  116. #------------------------------------------------------
  117. def postorder(self):
  118. """Returns the post order string of the BST."""
  119. info = ""
  120. if self.left:
  121. info += self.left.postorder()
  122. if self.right:
  123. info += self.right.postorder()
  124. info += str(self.value) + " "
  125. return info
  126.  
  127. def preorder(self):
  128. """Returns the pre order string of the BST."""
  129. info = ""
  130. info += str(self.value) + " "
  131. if self.left:
  132. info += self.left.preorder()
  133. if self.right:
  134. info += self.right.preorder()
  135. return info
  136. #------------------------------------------------------
  137. #------------------------------------------------------
  138. # Define the __contains__() method
  139. #------------------------------------------------------
  140. def __contains__(self, value):
  141. """Does the tree hold the value? So that "in" works."""
  142.  
  143.  
  144. return False
  145. #------------------------------------------------------
  146. #------------------------------------------------------
  147. def inorder(self):
  148. """Returns the in order string of the BST."""
  149. info = ""
  150. if self.left:
  151. info += self.left.inorder()
  152.  
  153. info += str(self.value) + " "
  154.  
  155. if self.right:
  156. info += self.right.inorder()
  157.  
  158. return info
  159. def __str__(self):
  160. """Return a string representation of the BST."""
  161. return self.get_string(0)
  162.  
  163. def get_string(self, spaces):
  164. string = ' ' * spaces + str(self.value)
  165. if self.left:
  166. string += '\n(l)' + self.left.get_string(spaces + 4)
  167. if self.right:
  168. string += '\n(r)' + self.right.get_string(spaces + 4)
  169. return string
  170.  
  171. Q4.
  172. # Binary Search Tree
  173.  
  174. class BST:
  175. """A Binary Search Tree (BST) class."""
  176.  
  177. def __init__(self, value, parent=None):
  178. """Construct a BST.
  179.  
  180. value -- the value of the root node
  181. parent -- the parent node (of this BST subtree)
  182. """
  183. self.value = value
  184. self.left = None
  185. self.right = None
  186. self.parent = parent
  187.  
  188.  
  189. def insert(self, value):
  190. """Insert value into the BST."""
  191. if value == self.value: # already in the tree
  192. return
  193. elif value < self.value:
  194. if self.left: # if it is not None
  195. self.left.insert(value)
  196. else:
  197. self.left = BST(value, parent=self) # create a new node
  198. else:
  199. if self.right:
  200. self.right.insert(value)
  201. else:
  202. self.right = BST(value, parent=self) # create a new node
  203.  
  204. def locate(self, value):
  205. """Return the node holding value."""
  206. if value == self.value:
  207. return self
  208. elif value < self.value and self.left:
  209. left_bst = self.left
  210. return left_bst.locate(value)
  211. elif value > self.value and self.right:
  212. right_bst = self.right
  213. return right_bst.locate(value)
  214. else:
  215. return None
  216.  
  217. def delete(self, value):
  218. """Delete value from the BST."""
  219. node = self.locate(value)
  220.  
  221. if node:
  222. left = node.left
  223. right = node.right
  224. if left and right: # both nodes are not None, i.e., two children
  225. node.delete_with_children()
  226. elif left or right: # one child
  227. node.delete_with_child()
  228. else: # no children
  229. node.delete_no_children()
  230.  
  231. def delete_no_children(self):
  232. if self.parent: #if parent exists
  233. if self.parent.left == self: #if is a left child
  234. self.parent.left = None
  235. else:
  236. self.parent.right = None
  237. else: # special case the root node
  238. self.value = None
  239.  
  240. def delete_with_child(self):
  241. if self.left:
  242. child = self.left
  243. else:
  244. child = self.right
  245. if self.parent:
  246. if self.parent.left == self:
  247. self.parent.left = child
  248. else:
  249. self.parent.right = child
  250. child.parent = self.parent
  251. else: # special case the root node
  252. self.replace(child)
  253.  
  254. def delete_with_children(self):
  255. replacement = self.right.min() # the successor
  256. successor_value = replacement.value
  257. self.delete(successor_value) # max of one child of this
  258. self.value = successor_value
  259.  
  260. def replace(self, other):
  261. """Replace this node with the values from other.
  262.  
  263. Also need to reattach other's children.
  264. """
  265. self.value = other.value
  266. self.left = other.left
  267. if self.left: self.left.parent = self
  268. self.right = other.right
  269. if self.right: self.right.parent = self
  270.  
  271. def min(self):
  272. """Returns the left most node of the BST."""
  273. min_node = self
  274. while min_node.left:
  275. min_node = min_node.left
  276. return min_node
  277. #------------------------------------------------------
  278. #------------------------------------------------------
  279. #Get the preorder string for the binary search tree
  280. #Get the postorder string for the binary search tree
  281. #------------------------------------------------------
  282. def postorder(self):
  283. info = ""
  284. if self.left:
  285. info += self.left.postorder()
  286.  
  287. if self.right:
  288. info += self.right.postorder()
  289.  
  290. info += str(self.value) + " "
  291.  
  292.  
  293. return info
  294.  
  295. def preorder(self):
  296. """Returns the pre order string of the BST."""
  297.  
  298. info = ""
  299. info += str(self.value) + " "
  300. if self.left:
  301. info += self.left.preorder()
  302.  
  303. if self.right:
  304. info += self.right.preorder()
  305.  
  306.  
  307. return info
  308.  
  309. #------------------------------------------------------
  310. #------------------------------------------------------
  311. # Define the __contains__() method
  312. #------------------------------------------------------
  313. def __contains__(self, value):
  314. if self.locate(value) == None:
  315. return False
  316. return True
  317. #------------------------------------------------------
  318. #------------------------------------------------------
  319. def inorder(self):
  320. """Returns the in order string of the BST."""
  321. info = ""
  322. if self.left:
  323. info += self.left.inorder()
  324.  
  325. info += str(self.value) + " "
  326.  
  327. if self.right:
  328. info += self.right.inorder()
  329.  
  330. return info
  331. def __str__(self):
  332. """Return a string representation of the BST."""
  333. return self.get_string(0)
  334.  
  335. def get_string(self, spaces):
  336. string = ' ' * spaces + str(self.value)
  337. if self.left:
  338. string += '\n(l)' + self.left.get_string(spaces + 4)
  339. if self.right:
  340. string += '\n(r)' + self.right.get_string(spaces + 4)
  341. return string
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!