1 Product Categorizer

In this assignment, you are expected to implement a categorizer class, namely ProductCategorizer, that takes in categorical data and maintains the categorical relationships such as parent-child and sibling relationships. ProductCategorizer will have two methods: def fill_tree(self): and def print_tree(self):. fill_tree will read categorical data from a text file and fill up an internally maintained general tree based on the structure that can be inferred from the data. The tree that will be used by ProductCategorizer will be an instance of LinkedTree, which you will implement in this assignment. The print_tree method will traverse the tree in a pre-order and post-order fashion and print the categorical data in a more proper way compared to the input file.

2 Code Templates In this assignment, we will provide some code templates that can boost your progress. Please find them in the tree.py file. You can make slight changes to the template if you would like, however, the expected functionality (adding nodes, traversals, filling and printing tree, etc.) should be in your code.

3 The LinkedTree Class This class should implement a general tree ADT by adopting a link-based approach. In doing so, you are expected to use the base class Tree whose implementation is provided in the Chapter 8 of the textbook (The code is provided in the tree.py file.). As you have already learned, by inheriting a base class, all the members and the methods of the base class are inherited to the child class, in other words, they become directly usable by the instances of child class. However, some of the methods of the Tree base class are not implemented, so you will implement them in the LinkedTree class. Also note that, as we covered in our lectures, we will have a distinction between the node and position objects. Nodes will contain the actual data and other references such as parent and children that form the tree. Positions are just pointers to the nodes of the tree, indicating their positions. Here you are not expected to change or improve the Position subclass and related _validate and _make_position methods. A linked tree is formed with nodes that are connected to each other. Nodes will be implemented with the _Node nested class. It should store only data members that point to element (the reference to the data stored), parent (reference to parent node, None for root), and a reference to the list that will be holding the children of the node. By convention, the _children reference should be None if a node does not have any children. Most of the methods of LinkedTree are the ADT operations that are common to any kind of trees: __len__, root, parent, num_children, children, is_root, is_leaf. You will implement two methods for adding a new node to the tree: _add_root and _add_nonroot_node, as their names speak for themselves, they will be used for adding the root and non-root nodes, respectively. However, you should hide away this detail from the users of your class. Due to that reason, you will also implement a (conventionally) public method, add_node, that is smart enough to decide whether to use _add_root or _add_nonroot_node method. The LinkedTree should also provide generators yielding the nodes according to well-known traversing algorithms. The _traverse_preorder method should yield nodes according to the pre-order traverse algorithm whilst _traverse_postorder should do the same with post-order traverse approach. Again, we would like to offer this functionality to the users of the LinkedTree class as a public method, namely all_nodes, which will take a parameter (mode) and decide whether to adopt pre-order or post-order traversal. The users of the LinkedTree should also be able to get the list of nodes that forms a path from a given position to root (get_path_to_root). And finally, given a position and a value, LinkedTree should be able to find the child node of position having the inquired value (find_child_by_value). For example, if position p has a child node c with value 23.4, the call find_child_by_value(p, 23.4) should return a Position object pointing to node c. 1 For this assignment, you are not expected to implement methods for node replacing or deletions. So, you can safely consider this tree as a write-only structure.

4 The ProductCategorizer Class ProductCategorizer is a simple class that has two basic operations: Read categorical data from a text file and print them out in pre- or post-oder manner. The fill_tree method should take a file path as a parameter and read the categorical data line by line. An example data file is provided in Assignment2Input.txt. In the input file, data looks like this: 1 World 2 World , Asia 3 World , Asia , China Each line in the file should be considered as a path in the tree starting from root to a particular node. For example, for the line World,Asia,China; World should be the root node, Asia must be one of its children, and China has to be a child of Asia. So the filling up the tree can be done in the following manner (You can do it in different ways as well if you would like to): Read each line of the input file in the order they are listed in the file and check whether the given path exists or not. If it exists do nothing, otherwise create the nodes in the tree such that the parent-child relationship that can be inferred from the input file exists in the tree. For example, for the example input file, after the first line, a root node with a string element World will be created. After the second line, a child node of root with a string element Asia will be created. An important point to mention is that the values maintained in the children of a particular node have to be distinct. In other words, there cannot be two children of a node with the same value. We should also be able to print out the content of our tree according post- and pre-order of the nodes into an output text file. For that reason, we will need to implement the print_tree method that will print out the tree in both post- and pre-order limit and write to a text file. Example output files are provided in the assignment page as Assignment2OutputPre.txt and Assignment2OutputPost.txt. The method should generate two output files for post- and pre-order traversals, and the hierarchy should be explicit in the output files with tabs (When deciding the number of tabs in a line, you may want to use the depth property of a node.).

5 Appendices This assignment document has four appendices: tree.py, Assignment2Input.txt, Assignment2OutputPre. txt, and Assignment2OutputPost.txt.