在二叉搜索樹中實現迭代器

Question

我通過在樹上進行inorder遍歷來保存樹中的鍵在數組中。

我在函數private void inOrder(Node node,K[] keys,int counter)中使用counter變量，並在每次添加後增加計數器變量的同時向數組中添加鍵。但問題是，由於遞歸，counter的值重置爲0.我也嘗試使counter變爲靜態，但它使問題更加複雜，並且也不能解決問題。

以下是完整的代碼。

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()); 
     } 

    } 

} 

的輸出低於

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 

Answer 1

代替使用我用一個ArrayList數組，並且它解決了這個問題。 以前代碼的問題是counter在遞歸調用inOrder期間用於重置爲0，因爲它是一個局部變量。 將其更改爲數組列表淘汰的計數器變量與add()功能，它解決了這個問題 下面是相同的代碼： -

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,parent; 

     public Node(){} 

     public Node(K k,V v,Node p){ 
      //System.out.println(k+" "+v+" "+p); 
      key=k; 
      value=v; 
      parent=p; 
     } 
    } 


    public class KeyIterator implements Iterator<K>{ 
     private ArrayList<K> keys; 
     private int counter; 

     public KeyIterator(){ 
      counter=0; 
      keys=new ArrayList<K>(); 
      inOrder(root,keys); 

      System.out.println("KeyIterator()"); 
      for(K k:keys) 
       System.out.print(k+" "); 
      System.out.println(); 

     } 

     public boolean hasNext(){ 
      return counter<keys.size(); 
     } 

     public K next(){ 
      return keys.get(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("H", 1); 
    b.put("D", 2); 
    b.put("I", 3); 
    b.put("B", 4); 
    b.put("E", 5); 
    b.put("A", 6); 
    b.put("C", 7); 
    b.put("F", 7); 
    b.put("G", 7); 
    b.put("L", 7); 
    b.put("I", 7); 
    b.put("J", 7); 
    b.put("N", 7); 
    b.put("M", 7); 
    b.put("O", 7); 

    Iterator<String> seer=b.iterator(); 
    while(seer.hasNext()){ 
     System.out.println(seer.next()); 
    } 

} 
}