Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Q1.
- 81 99 154 232
- Q2.
- 51 45 72 81 90 88 121 106 232 303 167
- Q3.
- # Binary Search Tree
- class BST:
- """A Binary Search Tree (BST) class."""
- def __init__(self, value, parent=None):
- """Construct a BST.
- value -- the value of the root node
- parent -- the parent node (of this BST subtree)
- """
- self.value = value
- self.left = None
- self.right = None
- self.parent = parent
- def insert(self, value):
- """Insert value into the BST."""
- if value == self.value: # already in the tree
- return
- elif value < self.value:
- if self.left: # if it is not None
- self.left.insert(value)
- else:
- self.left = BST(value, parent=self) # create a new node
- else:
- if self.right:
- self.right.insert(value)
- else:
- self.right = BST(value, parent=self) # create a new node
- def locate(self, value):
- """Return the node holding value."""
- if value == self.value:
- return self
- elif value < self.value and self.left:
- left_bst = self.left
- return left_bst.locate(value)
- elif value > self.value and self.right:
- right_bst = self.right
- return right_bst.locate(value)
- else:
- return None
- def delete(self, value):
- """Delete value from the BST."""
- node = self.locate(value)
- if node:
- left = node.left
- right = node.right
- if left and right: # both nodes are not None, i.e., two children
- node.delete_with_children()
- elif left or right: # one child
- node.delete_with_child()
- else: # no children
- node.delete_no_children()
- def delete_no_children(self):
- if self.parent: #if parent exists
- if self.parent.left == self: #if is a left child
- self.parent.left = None
- else:
- self.parent.right = None
- else: # special case the root node
- self.value = None
- def delete_with_child(self):
- if self.left:
- child = self.left
- else:
- child = self.right
- if self.parent:
- if self.parent.left == self:
- self.parent.left = child
- else:
- self.parent.right = child
- child.parent = self.parent
- else: # special case the root node
- self.replace(child)
- def delete_with_children(self):
- replacement = self.right.min() # the successor
- successor_value = replacement.value
- self.delete(successor_value) # max of one child of this
- self.value = successor_value
- def replace(self, other):
- """Replace this node with the values from other.
- Also need to reattach other's children.
- """
- self.value = other.value
- self.left = other.left
- if self.left: self.left.parent = self
- self.right = other.right
- if self.right: self.right.parent = self
- def min(self):
- """Returns the left most node of the BST."""
- min_node = self
- while min_node.left:
- min_node = min_node.left
- return min_node
- #------------------------------------------------------
- #------------------------------------------------------
- #Get the preorder string for the binary search tree
- #Get the postorder string for the binary search tree
- #------------------------------------------------------
- def postorder(self):
- """Returns the post order string of the BST."""
- info = ""
- if self.left:
- info += self.left.postorder()
- if self.right:
- info += self.right.postorder()
- info += str(self.value) + " "
- return info
- def preorder(self):
- """Returns the pre order string of the BST."""
- info = ""
- info += str(self.value) + " "
- if self.left:
- info += self.left.preorder()
- if self.right:
- info += self.right.preorder()
- return info
- #------------------------------------------------------
- #------------------------------------------------------
- # Define the __contains__() method
- #------------------------------------------------------
- def __contains__(self, value):
- """Does the tree hold the value? So that "in" works."""
- return False
- #------------------------------------------------------
- #------------------------------------------------------
- def inorder(self):
- """Returns the in order string of the BST."""
- info = ""
- if self.left:
- info += self.left.inorder()
- info += str(self.value) + " "
- if self.right:
- info += self.right.inorder()
- return info
- def __str__(self):
- """Return a string representation of the BST."""
- return self.get_string(0)
- def get_string(self, spaces):
- string = ' ' * spaces + str(self.value)
- if self.left:
- string += '\n(l)' + self.left.get_string(spaces + 4)
- if self.right:
- string += '\n(r)' + self.right.get_string(spaces + 4)
- return string
- Q4.
- # Binary Search Tree
- class BST:
- """A Binary Search Tree (BST) class."""
- def __init__(self, value, parent=None):
- """Construct a BST.
- value -- the value of the root node
- parent -- the parent node (of this BST subtree)
- """
- self.value = value
- self.left = None
- self.right = None
- self.parent = parent
- def insert(self, value):
- """Insert value into the BST."""
- if value == self.value: # already in the tree
- return
- elif value < self.value:
- if self.left: # if it is not None
- self.left.insert(value)
- else:
- self.left = BST(value, parent=self) # create a new node
- else:
- if self.right:
- self.right.insert(value)
- else:
- self.right = BST(value, parent=self) # create a new node
- def locate(self, value):
- """Return the node holding value."""
- if value == self.value:
- return self
- elif value < self.value and self.left:
- left_bst = self.left
- return left_bst.locate(value)
- elif value > self.value and self.right:
- right_bst = self.right
- return right_bst.locate(value)
- else:
- return None
- def delete(self, value):
- """Delete value from the BST."""
- node = self.locate(value)
- if node:
- left = node.left
- right = node.right
- if left and right: # both nodes are not None, i.e., two children
- node.delete_with_children()
- elif left or right: # one child
- node.delete_with_child()
- else: # no children
- node.delete_no_children()
- def delete_no_children(self):
- if self.parent: #if parent exists
- if self.parent.left == self: #if is a left child
- self.parent.left = None
- else:
- self.parent.right = None
- else: # special case the root node
- self.value = None
- def delete_with_child(self):
- if self.left:
- child = self.left
- else:
- child = self.right
- if self.parent:
- if self.parent.left == self:
- self.parent.left = child
- else:
- self.parent.right = child
- child.parent = self.parent
- else: # special case the root node
- self.replace(child)
- def delete_with_children(self):
- replacement = self.right.min() # the successor
- successor_value = replacement.value
- self.delete(successor_value) # max of one child of this
- self.value = successor_value
- def replace(self, other):
- """Replace this node with the values from other.
- Also need to reattach other's children.
- """
- self.value = other.value
- self.left = other.left
- if self.left: self.left.parent = self
- self.right = other.right
- if self.right: self.right.parent = self
- def min(self):
- """Returns the left most node of the BST."""
- min_node = self
- while min_node.left:
- min_node = min_node.left
- return min_node
- #------------------------------------------------------
- #------------------------------------------------------
- #Get the preorder string for the binary search tree
- #Get the postorder string for the binary search tree
- #------------------------------------------------------
- def postorder(self):
- info = ""
- if self.left:
- info += self.left.postorder()
- if self.right:
- info += self.right.postorder()
- info += str(self.value) + " "
- return info
- def preorder(self):
- """Returns the pre order string of the BST."""
- info = ""
- info += str(self.value) + " "
- if self.left:
- info += self.left.preorder()
- if self.right:
- info += self.right.preorder()
- return info
- #------------------------------------------------------
- #------------------------------------------------------
- # Define the __contains__() method
- #------------------------------------------------------
- def __contains__(self, value):
- if self.locate(value) == None:
- return False
- return True
- #------------------------------------------------------
- #------------------------------------------------------
- def inorder(self):
- """Returns the in order string of the BST."""
- info = ""
- if self.left:
- info += self.left.inorder()
- info += str(self.value) + " "
- if self.right:
- info += self.right.inorder()
- return info
- def __str__(self):
- """Return a string representation of the BST."""
- return self.get_string(0)
- def get_string(self, spaces):
- string = ' ' * spaces + str(self.value)
- if self.left:
- string += '\n(l)' + self.left.get_string(spaces + 4)
- if self.right:
- string += '\n(r)' + self.right.get_string(spaces + 4)
- return string
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement