Question
This assignment covers two basic topics: AVL Trees and Binary Heaps (specifically, min-heaps). Iterators (and traversals) are also an important part of the assignment.
Part 1: AVL Tree and Iterators
For the first part, you need to implement an AVL tree. In addition to the included breadth-first iterator, you will create two new iterators: one for preorder traversal, and one for inorder traversal (there is also a bonus for a postorder traversal. See below).
You are provided the code for a Binary Search Tree with an iterator (BinaryTree.java, BinaryNode.java, BinaryTreeIteratorBFS.java). You will write a new class (AVLTree.java) which extends the BinaryTree class. The AVLTree class will:
Override the 'add' method.
Include a function, preorder(), that creates an iterator on the AVL Tree that performs a
preorder traversal on the tree. Note: code to help you with this is included in the slides.
Include a function, inorder(), that creates an iterator on the AVL Tree that performs an
inorder traversal on the tree. Note: this is harder. Work it out on paper before writing it!
Bonus: Include a function, postorder(), that creates an iterator on the AVL Tree that performs
a postorder traversal on the tree. Note: This can be tricky. There's a small hint included in the BinaryNode.java class file.
Important: Your iterators can't simply do an entire traversal in advance, and keep all the values in some structure until they're needed. The iterators must actually traverse the tree progressively as next() is called.
(This also means you can't have it start over each time next() is called)
Part 2: Binary Heap
For the second part, you will be implementing a binary min-heap, called BinaryHeap.java, which will implement the included interface (MinHeap.java).
It will have two constructors: One that receives the capacity as its only parameter, and one without parameters that assumes a default capacity of 100.
You must also include an iterator for the heap. For this iterator, it should just run through the array, returning the items within it (however, it should not return the empty space at the beginning, and it should stop once it's reached the end of the actual stored values).
Of course, this implementation should use an array, not linked structures.
Note the requirement for generics and exceptions specified in the interface.
Note: You are strongly encouraged to create your own test harness to test your structures and iterators. However, this is not strictly required, as I will be using my own test harness.
As with the last assignment, it is absolutely imperative that you make your classes command-line friendly. For convenience, please don't use any package names. Don't submit anything other than .java source files (and .class files if you don't feel like deleting them) electronically. I should be able to use them from within the same directory as the files.
Also, the class names provided are not suggestions; they are mandatory.
Explanation / Answer
package AVLTree; 002 003 import java.util.Scanner; 004 import java.io.FileReader; 005 import java.io.BufferedReader; 006 import java.io.IOException; 007 import java.lang.Character; 008 009 public class AVLTreeDriver 010 { 011 public static void main(String[] args) 012 { 013 Scanner keyboard; 014 keyboard = new Scanner(System.in); 015 AVLTree myTree; 016 myTree = new AVLTree(); 017 018 int sentinel = 0; 019 020 021 while (sentinel != -1) 022 { 023 int menu = 0; 024 025 System.out.println("AVL Tree Main Menu"); 026 System.out.println(); 027 System.out.println("1. Reset AVL Tree To Empty"); 028 System.out.println("2. Insert New Node From Keyboard"); 029 System.out.println("3. Insert New Node From File"); 030 System.out.println("4. Print AVL Tree In Preorder Mode"); 031 System.out.println("5. Print AVL Tree In Inorder Mode"); 032 System.out.println("6. Print AVL Tree In Postorder Mode"); 033 System.out.println("7. Exit System"); 034 System.out.print("Please Make A Selection: "); 035 menu = keyboard.nextInt(); 036 037 switch (menu) 038 { 039 case 1: // Reset AVL Tree To Null 040 { 041 myTree = null; 042 break; 043 } 044 045 case 2: // Insert New Node from Keyboard 046 { 047 String temp; 048 System.out.println("Enter A Character To Insert To" + 049 " The Tree: "); 050 temp = keyboard.next(); 051 myTree.insert(temp); 052 break; 053 } 054 055 case 3: // Insert New Node From File 056 { 057 String fileName; 058 059 System.out.println("Enter A File To Grab Characters From: "); 060 fileName = keyboard.next(); 061 062 FileReader theFile; 063 BufferedReader fileIn = null; 064 char buffered; 065 String temp; 066 067 try 068 { 069 BufferedReader in = new BufferedReader(new FileReader(fileName)); 070 071 temp = in.readLine(); 072 myTree.insert(temp); 073 074 } 075 076 catch (IOException e) 077 { 078 System.out.println( e ); 079 } 080 081 finally 082 { 083 try 084 { 085 if( fileIn != null ) 086 fileIn.close(); 087 } 088 catch( IOException e) 089 { } 090 } 091 092 } 093 094 case 4: // PreOrder Print Tree 095 { 096 printPreorder(myTree); 097 break; 098 } 099 100 case 5: //InOrder Print Tree 101 { 102 printInorder(myTree); 103 break; 104 } 105 106 case 6: //PostOrder Print Tree 107 { 108 printPostorder(myTree); 109 break; 110 } 111 112 case 7: 113 { 114 sentinel = -1; 115 break; 116 } 117 } 118 } 119 120 System.out.println ("Thank You For Using The AVL Tree Program"); 121 } 122 123 private static void printPreorder(AVLTree tree) 124 { 125 AVLIterator temp = tree.getIterator(); 126 127 preorderRecursion(temp); 128 129 } 130 131 private static void preorderRecursion(AVLIterator temp) 132 { 133 System.out.println(temp.getValue()); 134 135 if(temp.getLeft() != null) 136 preorderRecursion(temp); 137 138 if (temp.getRight() != null) 139 preorderRecursion(temp); 140 } 141 142 private static void printInorder(AVLTree tree) 143 { 144 AVLIterator temp = tree.getIterator(); 145 146 inorderRecursion(temp, tree); 147 148 } 149 150 private static void inorderRecursion(AVLIterator temp, AVLTree tree) 151 { 152 if( temp.getLeft() != null) 153 inorderRecursion(temp, tree); 154 155 System.out.println(temp); 156 157 if (temp.getRight() != null) 158 inorderRecursion(temp, tree); 159 } 160 161 private static void printPostorder(AVLTree tree) 162 { 163 AVLIterator temp = tree.getIterator(); 164 165 postorderRecursion(temp, tree); 166 } 167 168 private static void postorderRecursion(AVLIterator temp, AVLTree tree) 169 { 170 if( temp.getLeft() != null) 171 postorderRecursion(temp, tree); 172 173 if( temp.getRight() != null) 174 postorderRecursion(temp, tree); 175 176 System.out.println(temp); 177 } 178 } BINARY HEAP: public AnyType findMin( ) 02 { 03 if( isEmpty( ) ) 04 throw new UnderflowException( ); 05 return array[ 1 ]; 06 } 07 08 /** 09 * Remove the smallest item from the priority queue. 10 * @return the smallest item, or throw an UnderflowException if empty. 11 */ 12 public AnyType deleteMin( ) 13 { 14 if( isEmpty( ) ) 15 throw new UnderflowException( ); 16 17 AnyType minItem = findMin( ); 18 array[ 1 ] = array[ currentSize-- ]; 19 percolateDown( 1 ); 20 21 return minItem; 22 /** 23 * Internal method to percolate down in the heap. 24 * @param hole the index at which the percolate begins. 25 */ 26 private void percolateDown( int hole ) 27 { 28 int child; 29 AnyType tmp = array[ hole ]; 30 31 for( ; hole * 2