I am saving the keys of the tree in an array by doing an inorder traversal on the tree.
I am using counter variable in the function private void inOrder(Node node,K[] keys,int counter) and add the keys to the array while incrementing the counter variable after each addition. The problem, however, is that because of recursion the value of counter is reset to 0. I also tried making counter static but it complicates the problem even more and doesn't solve it either.
Below is the full code.
package lab8;
import java.util.Set;
public interface Map61B<K, V> extends Iterable<K> {
/** Removes all of the mappings from this map. */
void clear();
/* Returns true if this map contains a mapping for the specified key. */
boolean containsKey(K key);
/* Returns the value to which the specified key is mapped, or null if this
* map contains no mapping for the key.
*/
V get(K key);
/* Returns the number of key-value mappings in this map. */
int size();
/* Associates the specified value with the specified key in this map. */
void put(K key, V value);
/* Returns a Set view of the keys contained in this map. */
Set<K> keySet();
/* Removes the mapping for the specified key from this map if present.
* Not required for Lab 8. If you don't implement this, throw an
* UnsupportedOperationException. */
V remove(K key);
/* Removes the entry for the specified key only if it is currently mapped to
* the specified value. Not required for Lab 8. If you don't implement this,
* throw an UnsupportedOperationException.*/
V remove(K key, V value);
}
package lab8;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
public class BSTMap<K extends Comparable<K>,V> implements Map61B<K,V> {
Node root;
int size;
class Node{
K key;
V value;
Node left,right;
public Node(){}
public Node(K k,V v){
key=k;
value=v;
}
}
public BSTMap(){}
/** Removes all of the mappings from this map. */
public void clear(){
root=null;
size=0;
}
/* Returns true if this map contains a mapping for the specified key. */
public boolean containsKey(K key){
return get(key) != null;
}
/* Returns the value to which the specified key is mapped, or null if this
* map contains no mapping for the key.
*/
public V get(K key){
if(size()==0)
return null;
Node temp=root;
//System.out.println("temp:"+temp+" "+temp.key);
while(temp!=null){
int comp=temp.key.compareTo(key);
if(comp==0)
return temp.value;
else if(comp<0)
temp=temp.left;
else
temp=temp.right;
}
return null;
}
/* Returns the number of key-value mappings in this map. */
public int size(){
return size;
}
//private recursive method
private Node put(Node node,K key,V value){
if(node==null)
return new Node(key,value);
int comp;
comp=key.compareTo(node.key);
if(comp==0)
return node;
else if(comp<0)
node.left=put(node.left,key,value);
else
node.right=put(node.right,key,value);
return node;
}
/* Associates the specified value with the specified key in this map. */
public void put(K key, V value){
root=put(root,key,value);
size++;
return;
}
public void printInOrder(){
if(size()==0){
System.out.println("list empty");
return;
}
inOrder(root);
}
private void printNode(Node node){
System.out.print("("+node.key+" "+node.value+")");
}
private void inOrder(Node node){
if(node==null)
return;
inOrder(node.left);
printNode(node);
inOrder(node.right);
}
private void inOrder(Node node,Set keySet){
if(node==null)
return ;
inOrder(node.left,keySet);
//System.out.println("Adding key:"+node.key);
keySet.add(node.key);
inOrder(node.right,keySet);
}
private void inOrder(Node node,K[] keys,int counter){
if(node==null)
return ;
inOrder(node.left,keys,counter);
System.out.println("Adding key to array at location:"+counter+" key:"+node.key);
keys[counter++]=node.key;
inOrder(node.right,keys,counter);
}
public Set<K> keySet(){
if(root==null)
return null;
Set<K> keys=new HashSet<K>();
inOrder(root,keys);
return keys;
}
public V remove(K key){
throw new UnsupportedOperationException();
}
public V remove(K key, V value){
throw new UnsupportedOperationException();
}
public class KeyIterator implements Iterator<K>{
private K[] keys;
private int counter;
public KeyIterator(){
keys=(K[])new Comparable[size];
//(K[])new Comparable[size];
inOrder(root,keys,counter);
System.out.println("Printing inside constrcutor");
for(int i=0;i<keys.length;i++)
System.out.print(keys[i]+" ");
System.out.println();
}
public boolean hasNext(){
return counter<keys.length;
}
public K next(){
return keys[counter++];
}
public void remove(){
}
}
public Iterator<K> iterator(){
Iterator<K> seer=new KeyIterator();
return seer;
}
public static void main(String[] args) {
BSTMap<String, String> a = new BSTMap<String, String>();
BSTMap<String, Integer> b = new BSTMap<String, Integer>();
b.put("C", 1);
System.out.println(b.get("C"));
b.put("A", 2);
b.put("B", 3);
b.put("G", 4);
b.printInOrder();
System.out.println();
System.out.println("keys are:"+b.keySet());
System.out.println("Printing via enhanced for loop:");
for(String str:b)
System.out.println(str);
//Above code is same as saying
System.out.println("Printing the legendary iterator:");
Iterator<String> seer=b.iterator();
while(seer.hasNext()){
System.out.println(seer.next());
}
}
}
The output is below
1
(A 2)(B 3)(C 1)(G 4)
keys are:[A, B, C, G]
Printing via enhanced for loop:
Adding key to array at location:0 key:A
Adding key to array at location:1 key:B
Adding key to array at location:0 key:C
Adding key to array at location:1 key:G
Printing inside constrcutor
C G null null
C
G
null
null
