COP 3530 Section U03 Spring 2017 MORE PROGRAMMING PROBLEMS ========================= Problem 1. ---------- In a binary tree, the same item can occur multiple times. Let's call that number the multiplicity of the item. Two binary tree are similar if they have the same number of items and for each item the multiplicity of the item in one tree is equal to its multiplicity in the other tree. For example, the two trees below are similar because they have the same set of items "Bill", "Che" and "Bilbo", and the multiplicity of each item is the same in both trees; "Bill" occurs 3 times, "Bilbo" twice and "Che" one time. Add the method public boolean isSimilar(BinaryNode other) to the class BinaryNode. The method returns true if this is similar to other and false if if it is not. Do not assume that T implements Comparable. Use equals to check if two items are equal. Do not assume that BinaryNode implements the Collection interface. You may use data structures such as lists and arrays and you may employ helper methods. Bill Bilbo / \ / \ / \ / \ Bill Che Bill Bilbo / / \ / \ / / \ / \ Bilbo Bill Bilbo Bill Che \ \ Bill The program: ------------ // see if this is similar to other // this means that they have the same items and each item // has the same multiplicity in both trees public boolean isSimilar(BinaryNode other) { if (other == null) return false; // put all items of this in the list l1 LinkedList l1 = new LinkedList<>(); addItems(l1); // put all items of other in l2 LinkedList l2 = new LinkedList<>(); other.addItems(l2); // check if the 2 list are equal return equals(l1,l2); } // add all items of this in the list l private void addItems(LinkedList list) { list.add(element); if (left != null) left.addItems(list); if (right != null) right.addItems(list); } // check if the lists l1 and l2 are equal private boolean equals(LinkedList l1, LinkedList l2 ) { if (l1 == null && l2 == null) return true; //both null if (l1 == null || l2 == null) return false; // only one is null if (l1.size() != l2.size()) return false; // for each item in l1 remove it from l2 for (T item : l1) if (! l2.remove(item)) return false; return true; } Problem 2. ---------- We define the postfix expressions as follows: 1. The lower case letters a, b, c, ... , z are prefix expressions. We call these expressions variables. 2. If E and F are postfix expressions, so is EF+. 3. If E and F are postfix expressions, so is EF*. 4. If E and F are postfix expressions, so is EF-. In the rules 2,3,4, the expressions E and F can be equal or different. Write the method public static BinaryNode buildTheTree(String in) that takes as input a postfix expression and outputs a binary tree whose postorder traversal is the postfix expression. For example, if postfixExp = "abc*+cd-a+-" buildTheTree(postfixExp) should generate the tree below. The postorder traversal of this tree is 'a', 'b' , 'c', '*', '+', 'c', 'd', '-', 'a', '+', '-' i.e. the array of characters of the string "abc*+cd-a+-". Throw an illegal argument exception if the input string is not a postfix expression. - / \ / \ + + / \ / \ / \ / \ a * - a / \ / \ / \ / \ b c c d The first program: ------------------ // build the tree from a postfix expression public static BinaryNode buildTheTree(String in) { // check if in is a postfix expression if (! isPostfix(in)) throw new IllegalArgumentException("not postfix"); // in is a postfix return buildTheTree(in, 0, in.length() -1); // call a helper method that forms the tree } // a helper method that forms a tree from the postfix // array slice arr[low:high] private static BinaryNode buildTheTree(String in, int low, int high) { if (low == high) // a leaf return new BinaryNode(in.charAt(low),null,null); // extract the slices that correspond to the two operands int count = 1; int i = high; while (count > 0) { if (isVariable(in.charAt(--i))) count-- ; // decrease the count else // it's an operator count++; } // form the root BinaryNode root = new BinaryNode<>(in.charAt(high), null, null); // find the right subtree root.setRight(buildTheTree(in, i, high - 1)); // find the left subtree root.setLeft(buildTheTree(in, low, i-1)); return root; } // check if in is a postfix expression private static boolean isPostfix(String in) { if (in == null || in.length() == 0) return false; // the number of variables is 1 plus the number of // operators, however count cannot be 0 until the very end int count = 1; int i = in.length() - 1; for (; i >= 0 && count > 0; i-- ) { if (isVariable(in.charAt(i))) count -= 1; else if (isOperator(in.charAt(i))) count += 1; else return false; // other character } return count == 0 && i == -1; } // check if x is a variable private static boolean isVariable(char x) { return x >= 'a' && x <= 'z'; } // check if x is an operator private static boolean isOperator(char x) { return x == '+' || x == '*' || x == '-'; } The second program: ------------------- Combine the testing for postfix with building the tree: // a simpler version of buildTheTree public static BinaryNode buildTheTree(String in) { // check if in is a postfix expression if ( in == null || in.length() % 2 == 0 ) throw new IllegalArgumentException("not postfix"); // in is a postfix return buildTheTree(in, 0, in.length() -1); // call a helper method that forms the tree } // a helper method that forms a tree from the postfix // array slice arr[low:high] private static BinaryNode buildTheTree(String in, int low, int high) { char curr = in.charAt(high); // if low = high, curr must be a variable // if low != high, curr must be an operator if (low == high && isVariable(curr) // a leaf return new BinaryNode(curr, null, null); if (low == high || isVariable(curr)) throw new IllegalArgumentException("Not a postfix form"); // extract the slices that correspond to the two operands int count = 1; int i = high; while (count > 0 && i > low + 1) { if (isVariable(in.charAt(--i))) count-- ; // decrease the count else // it's an operator count++; } // we cannot find the second operand if ( i < low + 1) throw new IllegalArgumentException("Not a postfix form"); // form the root BinaryNode root = new BinaryNode<>( curr, null, null); // find the left subtree root.setRight(buildTheTree(in, i, high - 1)); root.setLeft(buildTheTree(in, low, i-1)); return root; } // check if x is a variable private static boolean isVariable(char x) { return x >= 'a' && x <= 'z'; } Problem 3: ---------- Add the method public BinaryNode get(int i) to the BinaryNode class. The method returns the i-th node in the inorder traversal of the tree with root this. If i < 0 or i >= size() throw a no such element exception. You may use a helper method and/or an extra field, but at least one method must be recursive and you must not use the method size. The program: ------------ // get the i-th node in the inorder traversal public BinaryNode get (int i) { if (i < 0) throw new NoSuchElementException(); int[] arr = {-1}; // arr is a count BinaryNode out = get(arr, i); if (out == null) throw new NoSuchElementException(); return out; } // arr is counter that tells us how many nodes we processed so far // traverse the tree in inorder private BinaryNode get(int[] arr, int i) { // traverse the left subtree BinaryNode out = null; if (left != null) out = left.get(arr,i); // process root if (out != null) return out; // was found it in the left subtree arr[0] += 1; // increase the count if (arr[0] == i) return this; // it is the root // i was not found on the left and is not the root // process the right if ( right == null) return null; else // search the right subtree return right.get(arr,i); }