java - 在先序动态规划算法中打印最优二叉搜索树

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 是否在数组大小之内，并且其中存在节点。对左侧和右侧执行相同的操作。