For the written section of this assignment, type up your answers and submit a computer based document to us. You can submit MS Word doc files, pdf files, or txt files.
Use book downloaded
1 Problem 1: Weiss 4.6 - We're looking for a full induction proof
4.6 A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.
2 Problem 2: Weiss 4.9 - In part a show the tree after each insert - a total of 8 trees. In part b, we're doing full deletion, not lazy deletion. Show the tree after each step of the removal.
4.9 a. Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search tree. b. Show the result of deleting the root.
3 Problem 3: Show the same sequence of inserts as listed in the previous problem, except this time show the insertions into an AVL tree. Make sure to show each rotation. Show both steps involved in each double rotation.
4 Problem 4: Assume that you are given both the preorder and postorder traversal of some binary tree t. Prove that this information, taken together, is not necessarily sufficient to reconstruct t uniquely, even if each value in t occurs only once.
5 Problem 5 : Based on Weiss 4.16 - Describe any modifications that you would need to make to the BinaryNode itself, and then show the implementation for findMin. You don't actually have to give us a full working class, only a description of the modification plus the findMin code.
4.16 Redo the binary search tree class to implement lazy deletion. Note carefully that this affects all of the routines. Especially challenging are findMin and findMax , which must now be done recursively.
For the programming portion of the assignment, please submit only your .java files and your README.txt. Your code should be well commented. In addition please include a detailed README.txt file which indicates exactly what files you are submitting, what problem they solve, and how to compile and run them (provide specific command line instructions).
1 Implementing Expression Trees:Implement a class called ExpressionTree . The constructor to ExpressionTree will take in a String that contains a postfix expression. The operands will be integers and the binary operators will be restricted to +, -, *, and divide. Individual tokens, that is the operands and operators, will be delimited by spaces. So for example:34 2 - 5 *would mean (34-2)*5.Your constructor will run the stack based algorithm we discussed in class to build an expression tree. ExpressionNodes will be a nested class within ExpressionTree. You may use any code posted on canvas or from the Weiss textbook as a starting point for this class. As a stack data structure, you can either use java.util.LinkedList, your own class from homework 2, or the MyStack.java file from the sample solution for homework 2. Once you have the ExpressionTree constructed you should provide the following four methods:
public int eval() - this method, when invoked on an expression tree object will return the integer value associated with evaluating the expression tree. It will need to call a private recursive method that takes in the root.
public String postfix() - this method, when invoked on an expression tree object will return a String that contains the corresponding postfix expression. It will need to call a private recursive method that takes in the root.
public String prefix() - this method, when invoked on an expression tree object will return a String that contains the corresponding prefix expression. It will need to call a private recursive method that takes in the root.
public String infix() - this method, when invoked on an expression tree object will return a String that contains the corresponding correct infix expression. Keep in mind that parenthesis will be needed (excessive parenthesis will be tolerated as long as it is correct). It will need to call a private recursive method that takes in the root.
2 Write a class called Problem1.java that instantiates an expression, and demonstrate your methods.
3 Write a command line application Problem2.java that indexes the words contained in a text file. Your program should go through the input file line by line. For each line, it extracts each word, and insert that word, along with it's line number into an AVL tree. Each element of the AVL tree should contain a unique word and a linked list of line numbers where that word occurs. To implement this AVL tree, you can use the AVLTree code from the textbook as a starting point (available here -- note that you must include the UnderFlowException class, which is available here ). Modify this file directly and add the following functionality:
Make sure the elements in the AvlTree are pairs of a word and a linked lists storing line numbers. The relative order of elements in the data structure should depend on the word only.
Write the method public void indexWord(String word, int line) that adds an occurrence of the word word in line line. If a word already exists in the AVL Tree, simply add the new line number to the existing node. If a word appears on the same line twice, it should only have one entry in the list for that line.
Write the method public List getLinesForWord(String word) that looks up a word and returns a list of lines in which it occurs.
Write the method public void printIndex() the prints out each unique word that is stored in the Avl tree along with a list of line numbers in which that word appears.
4 Finally, the main method in Problem2.java should create an instance of your AvlTree and uses it to indexes the words contained in a text file (provided to the program as a command line argument). Ignore case in the input text (insert everything as lower case), and ignore all punctuation. When indexing has finished, the program should call the printIndex method to display a list of unique words in the text file and the line numbers in which that word occurs.
5 You may test your program on the attached text file frank.txt .