Tree Sort ISTA 350 Hw10,

Introduction. This homework is intended to introduce you to the tree data structure and recursion. Trees are a critical part of the software infrastructure of civilization. Recursion – a function calling itself – is an essential programming tool. The tree you will be creating is called a binary search tree (BST). Defining characteristics of BST's include: • Each Node has at most two children. • The datum in a Node's left child is less than the datum in the Node itself. • The datum in a Node's right child is greater than the datum in the Node itself. Once you complete this module, you can create a sorted copy of a list with the code sorted_list = BST(starting_list).sort(). Instructions. Create a module named hw10.py. Below is the spec for six methods comprising two classes. Implement them and upload your module to the D2L dropbox. Testing. Download hw10_test.py and put it in the same folder as your hw10.py module. Run it from the command line to see your current correctness score. Each of the 6 methods is worth 16.7% of your correctness score. You can examine the test module in a text editor to understand better what your code should do. The test module is part of the spec. The test file we will use to grade your program will be different and may uncover failings in your work not evident upon testing with the provided file. Add any necessary tests to make sure your code works in all cases. Documentation. Your module must contain a header docstring containing your name, your section leader’s name, the date, ISTA 350 Hw10, and a brief summary of the module. Each method must contain a docstring. Each docstring should include a description of the method's purpose, the name, type, and purpose of each parameter, and the type and meaning of the method's return value. Grading. Your module will be graded on correctness, documentation, and coding style. Code should be clear and concise. You will only lose style points if your code is a real mess. Include inline comments to explain tricky lines and summarize sections of code (not necessary on this assignment). Collaboration. Collaboration is allowed. You are responsible for your learning. Depending too much on others will hurt you on the tests. “Helping” others too much harms them in reality. Cite any sources/collaborators in your header docstring. Leaving this out is dishonest. class Node: Each Node object can be visualized as follows: In order to use a tree made from Node objects to sort its data, all of the datum fields must contain comparable types. The entries field tells us how many times datum has been inserted into the tree. Node objects can be linked to form a tree: init: The initializer takes one argument, the item to be stored in the Node. What should entries be initialized to? The Node's children are initialized to None. insert: This method takes one argument, an item to be added to the subtree with self as its root. If the Node contains the same item, increment entries. If the item belongs in the left subtree but the subtree is empty, link to a new Node containing the item. If the left subtree is not empty, recursively call insert on self.left. Similarly for the right subtree. sort: This is method takes a list as an argument and alters it in place, in the course of an inorder traversal of the tree. If there is a left subtree, recursively call sort on it. Append datum to the list entries times. Take care of the right subtree. def __repr__(self): ''' reverse inorder traversal ''' result = (repr(self.datum) + ' ') * self.entries if self.right: result = repr(self.right) + result if self.left: result += repr(self.left) return result def fill_list_2D(self, lsts, level, column): ''' This is a helper method for filling a pre-initalized 2-dimensional list of lists of strings with the elements of a tree. ''' lsts[level][column] = (str(self.datum) + '(' + str(self.entries)+\ ')').zfill(6) if self.left: self.left.fill_list_2D(lsts, level + 1, 2 * column) if self.right: self.right.fill_list_2D(lsts, level + 1, 2 * column + 1) class BST: init: The initializer takes one list argument with a default argument of None. The tree contains one field, a Node called root. Initialize it to None. If the list argument contains data, insert it into the tree in the order in which it occurs in the list. insert: This method takes one argument, the item to be inserted. If root exists, call Node's insert method on it. Otherwise, assign a new Node containing the item to root. sort: Initialize a list. If root exists, call Node's sort method on it. Return the list. def __repr__(self): ''' Works if all entries < 10, all data are ints and < 1000 and -99. ''' if not self.root: return 'Empty tree' h = self.height() w = 2**h # max possible nodes in the highest level tree_list = [] for i in range(h + 1): tree_list.append(['******'] * 2**i) self.root.fill_list_2D(tree_list, 0, 0) return BST._repr(tree_list, w * 6 + (w - 1) * 2, h) @staticmethod def _repr(tree_list, w, h): for i in range(len(tree_list)): num_items = 2**i leading = 2**(h - i + 2) - 4 if i == 0: tree_list[0] = ' ' * leading + tree_list[0][0] elif i < len(tree_list) - 1: spacer = ' ' * (round((w - num_items * 6 - leading * 2) // (num_items - 1))) tree_list[i] = ' ' * leading + spacer.join(tree_list[i]) else: tree_list[-1] = ' '.join(tree_list[-1]) return '\n'.join(tree_list)