# DS Blank, Fall 2010, Data Structures # Questions 1 and 2 Solutions import random class Tree: def __init__(self, value=None): self.value = value self.left = None self.right = None def insert(self, value): if value < self.value: # insert on left if self.left == None: self.left = Tree(value) else: self.left.insert(value) else: # insert on right if self.right == None: self.right = Tree(value) else: self.right.insert(value) def contains(self, value, count=0): if value == self.value: return (True, count + 1) elif value < self.value: if self.left is None: return (False, count + 1) return self.left.contains(value, count + 1) elif value > self.value: if self.right is None: return (False, count + 1) return self.right.contains(value, count + 1) def to_list(self): retval = [] if self.left is not None: retval += self.left.to_list() retval += [self.value] if self.right is not None: retval += self.right.to_list() return retval def from_list(self, list): if len(list) != 0: pos = len(list)//2 left = list[:pos] right = list[pos+1:] if self.value == None: self.value = list[pos] else: self.insert(list[pos]) self.from_list(left) self.from_list(right) def size(self): if self.left == None: left = 0 else: left = self.left.size() if self.right == None: right = 0 else: right = self.right.size() return left + right + 1 def makeRandom(max_value=100000000): return int(random.random() * max_value) tree1 = Tree(makeRandom()) for i in range(999): tree1.insert(makeRandom()) print tree1.contains(654) items = tree1.to_list() tree2 = Tree() tree2.from_list(items)