在預購動態編程算法中打印最優二叉搜索樹

Question

我剛剛完成了計算OBST的平均成本，並且我知道我正確計算了它。我的下一個任務是按預定順序打印樹。我試圖在這個使用遞歸，但似乎無法動搖空指針錯誤。

這裏是我的代碼：

public class OBST { 
static String[] keysA; 
static Integer[][] root; 

public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 
     int tot = sc.nextInt(); 
     HashMap<String, Double> hm = new HashMap<String, Double>(); 

     int uniqNum = 0; 
     String[] rawInput = new String[tot]; 

     for(int i=0; i<tot; i++) { 
      String tmp1 = sc.next(); 
      if(i==0) { 
       hm.put(tmp1, 1.0); 
       uniqNum += 1.0; 
      } else if(i != 0) { 
       if(!hm.containsKey(tmp1)) { 
        hm.put(tmp1, 1.0); 
        uniqNum += 1.0; 
       } else { 
        Double tmpfreq = 0.0; 
        tmpfreq = hm.get(tmp1); 
        hm.put(tmp1, (tmpfreq + 1.0)); 
       } 
      } 
     } 
     Set<String> keys = hm.keySet(); 
     keysA = keys.toArray(new String[uniqNum]); 
     Double[] freqsA = new Double[uniqNum]; 
     Arrays.sort(keysA); 
     for(int i=0; i<uniqNum; i++) { 
      Double tmp = 0.0; 
      String tmpK = keysA[i]; 
      tmp = hm.get(tmpK); 
      tmp = tmp/tot; 
      freqsA[i] = tmp; 
     } 
     Double[][] eee = new Double[uniqNum+2][uniqNum+1]; 
     Double[][] www = new Double[uniqNum+2][uniqNum+1]; 
     //matrix to store optimal structure 
     root = new Integer[uniqNum+1][uniqNum+1]; 
     for(int i=1; i<uniqNum+2; i++) { 
      eee[i][i-1] = 0.0; 
      www[i][i-1] = 0.0; 
     } 
     for(int l=1; l<uniqNum+1; l++) { 
      for(int i=1; i<=uniqNum-l+1; i++) { 
       int j = i + l - 1; 
       eee[i][j] = Double.MAX_VALUE; 
       www[i][j] = www[i][j-1] + freqsA[j-1]; 
       for(int r=i; r<=j; r++) { 
        Double t = eee[i][r-1] + eee[r+1][j] + www[i][j]; 
        if(t<eee[i][j]) { 
         eee[i][j] = t; 
         root[i][j] = r-1; 
        } 
       } 
      } 
     } 
     //total cost 
     System.out.println(eee[1][uniqNum]);  
     printTree(1,uniqNum-1,-1, ""); 
} 


public static void printTree(int min, int max, int parent, String s) { 
    int r = root[min][max]; 
    if(parent == -1) { 
     System.out.println(keysA[r] + " is root"); 
    } else if(min < parent) { 
     System.out.println(keysA[r] + " is the left child of " + s); 
    } else { 
     System.out.println(keysA[r] + " is the right child of " + s); 
    } if(min < max) { 
     printTree(min,r,r+1,keysA[r]); 
     printTree(r+1,max,r,keysA[r]); 
    } 
} 
} 

我的問題是在方法打印樹。

Answer 1

看起來你沒有正確地檢查你的邊界。如果沒有左邊或右邊的孩子，你不應該打印那一邊。因此請確保您檢查r + 1是否在數組大小內，並且還有一個節點存在。左右兩邊都是一樣的。