Imported Code

Project Code

import random class treeNode: def __init__(self): # initially, all are set to None values, so we can identify an uninitialised node when performing a search / # insert self.value = None self.leftNode = None self.rightNode = None def setValue(self, i): # when we set the value of a node, we also create sub-nodes on the left and right, so we can traverse past the\ # node more easily self.value = i self.leftNode = treeNode() self.rightNode = treeNode() def _insert_array(A): # first we create the base node as an uninitialised node baseNode = treeNode() for i in A: # for each element in the array we look for an uninitialised node on our walk - we start at the base, and we # place the number in the first uninitialised node we find currentNode = baseNode while currentNode.value != None: # while we are still looking for an uninitialised node if currentNode.value > i: # go left currentNode = currentNode.leftNode else: # go right currentNode = currentNode.rightNode # breaking the while loop means we have found a node with no value, so we now set the value (also creating new # blank nodes beneath) and go to the next element of the array currentNode.setValue(i) return baseNode def insert_array(filename): # open the file f = open(filename) # read the numbers l = f.readline() # strip out whitespace and newline and make an array l = l.split() A = [] for i in l: # convert from strings to ints A.append(int(i)) # make the tree return _insert_array(A) def search_print(k,T): # start at the base of the tree currentNode = T # the base of the tree will always be step 1 findString = (currentNode.value).__str__() while True: if currentNode.value == k: # we found it! Let the world know by printing the path we took, then returning for praise print(findString) return if currentNode.value == None: # it isn't here! Let the world know by printing our disappointment, then returning for commiseration print("the input number was not found in the BST") return if currentNode.value > k: # go left currentNode = currentNode.leftNode else: # go right currentNode = currentNode.rightNode # add the current node (that we haven't yet checked) to the path we took, then keep on keeping on findString += (" -> " + (currentNode.value).__str__()) def permute_array(A): for i in range(len(A)): # for each element, find a random element between this and the last element of the array k = random.randint(i, (len(A) - 1)) # swap them (incidentally, I do like that python allows this to do an array swap) A[i], A[k] = A[k], A[i] # ship the list back return A def height_of_node(T): # recursively identify the height of a node if T.value == None: # we have gone past the end! We're in a leaf that doesn't even exist, so head back up return (-1) # return the maximum height of the left and right nodes, and add 1 for this node. Note that uninitialised nodes # underneath cause the height of this node to be 0 (aka a leaf) as expected return (max(height_of_node(T.leftNode), height_of_node(T.rightNode)) + 1) def height_randomBST(N): # create the list, from 1 to N A = list(xrange(1, N+1)) # throw the list about a bit A = permute_array(A) # create the tree from the thrown-about list T = _insert_array(A) # go for a walk down the tree to find its height print(height_of_node(T).__str__()) return T

Commands

tree = height_randomBST(10) search_print(4, tree) search_print(6, tree) search_print(11, tree)

Run

Output