CMPS 212 Final, Spring 2013

import java.util.ArrayList; //Ghassan Fakher /* Consider a Binary Search Tree (BST) where each node contains a 'key' attribute and a 'data' attribute. The BST is ordered according to the key (assume that no two keys are the same key). You are provided with a Node class and BST class with some methods already implemented. You should impement 7 methods iteratively or recursively (check below). You are given a driver and its corresponding output. You can modify the methods' signatures if you need to. */ public class BST { public Node root; /* DO NOTHING HERE */ public Node findIterative(Node startNode, double key) { Node current = startNode; while(current.key != key) { if(key < current.key) // go left? current = current.leftChild; else // or go right? current = current.rightChild; if(current == null) // if no child, return null; // didn't find it } return current; // found it } /* DO NOTHING HERE */ public Node findRecursive(Node node, double key) { if (node == null) return null; else if (node.key == key) return node; else if (key < node.key) return findRecursive(node.leftChild, key); else return findRecursive(node.rightChild, key); } /* DO NOTHING HERE */ public void insert(Node newNode) { if(root==null) // no node in root root = newNode; else // root occupied { Node current = root; // start at root Node parent; while(true) { parent = current; if(newNode.key < current.key) { // go left? current = current.leftChild; if(current == null) { // if end of the line parent.leftChild = newNode; return; } } // end if go left else { // or go right? current = current.rightChild; if(current == null) { // if end of the line parent.rightChild = newNode; return; } } // end else go right } // end while } } /* DO NOTHING HERE */ public void inOrderPrint(Node node) { if (node != null) { inOrderPrint(node.leftChild); System.out.println(node); inOrderPrint(node.rightChild); } } /* METHOD-1: Returns the Node with the maximum key */ public Node maximum(){ return maximum(root);} private Node maximum(Node root){ while(root.rightChild != null){ root = root.rightChild;} return root; } /* METHOD-2: Returns true if tree is Full, false otherwise. A full binary tree is a tree in which every node other than the leaves has two children. Or, perhaps more clearly, every node in a binary tree has exactly 0 or 2 children. */ public boolean isFullTree(Node node) { if(node == null) return true; else{ if(node.leftChild != null && root.rightChild==null){ return false;} else if(node.leftChild == null && root.rightChild!=null) {return false;} else if(node.rightChild != null && node.leftChild != null) { return isFullTree(node.rightChild)&isFullTree(node.leftChild);} else {return true;} } } /* METHOD-3: Returns true if tree is a BST, false otherwise. */ public boolean isBST(Node node) { return isBST(node, false); } private boolean isBST(Node node, boolean bst) { if(node.rightChild != null){ if(node.key<node.rightChild.key){bst = true;} else bst = false; bst = bst & isBST(node.rightChild, bst); } else bst = true; if(node.leftChild !=null){ if(node.key > node.leftChild.key){bst = true;} else bst = false; bst = bst & isBST(node.leftChild, bst);} else bst = true; return bst; } /* METHOD-4: Returns true if both trees are similar in keys and data, false otherwise */ public boolean areSimilar(Node node1, Node node2){ return areSimilar(node1, node2, false); } private boolean areSimilar(Node node1, Node node2, boolean similar){ if((node1.key==node2.key) && (node1.data == node2.data)){similar = true;} else similar = false; if(node1.rightChild != null && node2.rightChild != null){ similar = similar & areSimilar(node1.rightChild, node2.rightChild, similar); } if(node1.leftChild != null && node2.leftChild != null){ similar = similar & areSimilar(node1.leftChild, node2.leftChild, similar); } return similar; } /* METHOD-5: Traverses the tree and returns the number of nodes traversed */ public static int treeSize(Node root) { return treeSize(root, 0); } private static int treeSize(Node root, int size){ if(root != null){size++;} if(root.leftChild != null){size = treeSize(root.leftChild, size);} if(root.rightChild!=null){size = treeSize(root.rightChild, size);} return size; } /* METHOD-6: Traverses the tree and returns the sum of the data attributes */ public static double treeSum(Node root) { return treeSize(root, 0.0); } private static double treeSize(Node root, double sum){ if(root != null){sum += root.data;} if(root.leftChild != null){sum = treeSize(root.leftChild, sum);} if(root.rightChild!=null){sum = treeSize(root.rightChild, sum);} return sum; } /* METHOD-7: Traverses the tree and returns its heigth */ public static int treeHeight(Node root) { ArrayList<Integer> heights = new ArrayList<Integer>(); //store all the heights in an array list then return the max heights= treeHeight(root, 0, heights); return maxHeight(heights); } private static ArrayList<Integer> treeHeight(Node root, int height, ArrayList<Integer> heights) { if(root!=null) height ++; if(root.leftChild==null && root.rightChild==null) {heights.add(height);} //we reach a leaf if(root.leftChild != null && root.rightChild==null) {treeHeight(root.leftChild, height, heights);} if(root.rightChild != null && root.leftChild==null) {treeHeight(root.rightChild, height, heights);} return heights; } private static int maxHeight(ArrayList<Integer> heights) { int max = heights.get(0); for(int i = 0; i < heights.size(); i++) { if(heights.get(i) > max) max = heights.get(i); } return max; } public static void main(String args[]) { BST t = new BST(); t.insert(new Node(1001, 92.5)); t.insert(new Node(4001, 72.5)); t.insert(new Node(10, 32.0)); t.insert(new Node(101, 2.9)); t.insert(new Node(402, 56.2)); t.insert(new Node(5000, 97.7)); t.insert(new Node(10000, 79.3)); t.insert(new Node(3500, 92.5)); System.out.println("in order print of tree:"); t.inOrderPrint(t.root); System.out.println(); System.out.println("finding node 402 iteratively : " + t.findIterative(t.root, 402)); System.out.println(); System.out.println("finding node 402 recursively : " + t.findRecursive(t.root, 402)); System.out.println(); System.out.println("finding node 2000 iteratively : " + t.findIterative(t.root, 2000)); System.out.println(); System.out.println("finding node 2000 recursively : " + t.findRecursive(t.root, 2000)); // Method-1 System.out.println(); System.out.println("node with maximum key : " + t.maximum()); // Method-2 System.out.println(); System.out.println("is this a full tree? " + t.isFullTree(t.root)); // Method-3 System.out.println(); System.out.println("is this a BST? " + t.isBST(t.root)); t.root.key = 5; // change the tree System.out.println(); System.out.println("is this a BST? " + t.isBST(t.root)); t.root.key = 1001; // change the tree back to its original state // Method-4 BST t2 = new BST(); t2.insert(new Node(1001, 92.5)); t2.insert(new Node(4001, 72.5)); t2.insert(new Node(10, 32.0)); t2.insert(new Node(101, 2.9)); t2.insert(new Node(402, 56.2)); t2.insert(new Node(5000, 97.7)); t2.insert(new Node(10000, 79.3)); t2.insert(new Node(3500, 92.5)); System.out.println(); System.out.println("are these similar trees (same keys and data)? " + t.areSimilar(t.root, t2.root)); BST t3 = new BST(); t3.insert(new Node(1011, 99.5)); t3.insert(new Node(4001, 72.5)); t3.insert(new Node(10, 32.0)); t3.insert(new Node(101, 2.9)); t3.insert(new Node(402, 56.2)); t3.insert(new Node(6000, 90.7)); t3.insert(new Node(10000, 79.3)); t3.insert(new Node(3500, 92.5)); System.out.println(); System.out.println("are these similar trees (same keys and data)? " + t.areSimilar(t.root, t3.root)); // Method-5 System.out.println(); System.out.println("size of tree (number of nodes) : " + t.treeSize(t.root)); // Method-6 System.out.println(); System.out.println("sum of tree (sum of data values) : " + t.treeSum(t.root)); // Method-7 System.out.println(); System.out.println("tree height : " + t.treeHeight(t.root)); } } /* THE EXPECTED OUTPUT FOR THIS DRIVER LOOKS AS FOLLOWS: in order print of tree: 10 32.0 101 2.9 402 56.2 1001 92.5 3500 92.5 4001 72.5 5000 97.7 10000 79.3 finding node 402 iteratively : 402 56.2 finding node 402 recursively : 402 56.2 finding node 2000 iteratively : null finding node 2000 recursively : null node with maximum key : 10000 79.3 is this a full tree? false is this a BST? true is this a BST? false are these similar trees (same keys and data)? true are these similar trees (same keys and data)? false size of tree (number of nodes) : 8 sum of tree (sum of data values) : 525.6 tree height : 3 */ import java.util.ArrayList; public class CustomFibonacci { public static void main(String[] args) { customFibo(14); } public static void customFibo(int n) { ArrayList<Integer> fibo = new ArrayList<Integer>(); if(n < 5) { for(int i = 1; i <= n; i++) { fibo.add(i); } System.out.print(fibo.get(0)); for(int i = 1; i < n; i++) { System.out.print(", " + fibo.get(i)); } } else { for(int i = 1; i <= 4; i++) { fibo.add(i); } customFibo(n, fibo, 0); } } private static void customFibo(int n, ArrayList<Integer> fibo, int current) { if(n > fibo.size()) { fibo.add(fibo.get(current) + fibo.get(current + 1)); current ++; customFibo(n, fibo, current); } else { System.out.print(fibo.get(0)); for(int i = 1; i < fibo.size(); i++) { System.out.print(", " + fibo.get(i) ); } } } } import javax.swing.text.html.HTMLDocument.Iterator; // REMOVE THE TWO COMMENTS BELOW WHEN YOU ARE DONE WITH IMPLEMENTING THE "reorder" METHOD public class Reordering { // a test client public static void main(String[] args) { Queue<Integer> q = new Queue<Integer>(); q.enqueue(1); q.enqueue(2); q.enqueue(-2); q.enqueue(4); q.enqueue(-5); q.enqueue(8); q.enqueue(-8); q.enqueue(12); q.enqueue(-15); q.enqueue(23); System.out.println(q); reorder(q); // you should implement the following method System.out.println(q); // this should print the new ordered list } public static void reorder(Queue<Integer> q) { //we will have to iterate this queue from front, when we encounter a negative number we enqueue it java.util.Iterator<Integer> itr = q.iterator(); Queue<Integer> pos = new Queue<Integer>(); Queue<Integer> neg = new Queue<Integer>(); for(int i = q.size(); i > 0; i--) { if(itr.next() < 0) { q.enqueue(q.dequeue()); } else { } } for(int i = 0; i < neg.size(); i++) { q.enqueue(neg.dequeue()); } for(int i = 0; i < pos.size(); i++) { q.enqueue(pos.dequeue()); } System.out.println(q.toString()); } }