Java - 利用遞迴來計算階層結構的總合

也許我們可能會碰到一種階層式的組織，如代號31 => 3101 + 3102 + 3103等，如此一來要得

到31的和，只要有其餘三個代號數字的加總即可! 因此，在這邊主要是探討假設有很多層的

情況，依循剛剛的組織設定，如何計算上層代號的和，透過底層代號所代表的數字去計算!

樹狀圖如下：

在這邊會利用Java HashMap來組成對應的階層關係，如下：

static Map<String, List<String>> h2subh = new TreeMap<String, List<String>>();
static Map<String, Integer> h2num = new HashMap<String, Integer>();
....
String h1[] = {"31"};
String h2_1[] = {"3101", "3102"};
String h3_1[] = {"3101001", "3101002"};
String h3_2[] = {"3102001", "3102002"};
String h4_1[] = {"3101001000", "3101001001"};
String h3Arr[] = {"3101001000", "3101001001","3101002","3102001", "3102002"};
int hNum[] = {11,22,33,12,31};
int i = 0;
h2subh.put(h1[0], Arrays.asList(h2_1));
h2subh.put(h2_1[0], Arrays.asList(h3_1));
h2subh.put(h2_1[1], Arrays.asList(h3_2));
h2subh.put(h3_1[0], Arrays.asList(h4_1));
System.out.println(h2subh.toString());

for(String h : h3Arr){
    h2num.put(h, hNum[i++]);
}
System.out.println(h2num.toString());

輸出後的結果如下圖，第一行為對應的關係；第二行為底層對應的數字!

接下來，就是如何利用底層的數字來求得上階層的數字：

for(String k : h2subh.keySet()){
    System.out.println("計算"+k+"對應的數字");
    h2num.put(k, calHierarchy(k));
    System.out.println("============================");
}
System.out.println(h2num.toString());

public static int calHierarchy(String key){
    int sum = 0;
    if(h2num.get(key) == null){
        System.out.println(key+"不存在對應的數字!");
        for(String k : h2subh.get(key)){
            System.out.println("取出"+key+"的下層結構"+k);
            h2num.put(k, calHierarchy(k));
            sum += h2num.get(k);
        }
        System.out.println(key+"對應的數字經計算="+sum);
        return sum;
    }else{
        System.out.println(key+"對應數字已存在="+h2num.get(key));
    }
    return h2num.get(key);
}

執行後結果：

一開始，31進入後先判斷是否有存在對應數字

若否，則取出31的所屬3101，再次呼叫method，判斷是否有對應的數字

若否，則取出對應的所屬3101001，再次呼叫method，判斷是否有對應的數字

若否，則取出對應的所屬3101001000，再次呼叫method，判斷是否有對應的數字

得到3101001000對應數字已存在=> 11

回傳後，h2num.put(k, calHierarchy(k));  //k = 3101001000, value = 11

取出3101001的下層結構3101001001，再次呼叫method，判斷是否有對應的數字

得到3101001001對應數字已存在=>22

回傳後，h2num.put(k, calHierarchy(k));  //k = 3101001001, value = 22

跳出迴圈

回傳sum的總和 => 11 + 22 = 33，h2num.put(k, calHierarchy(k));  //k = 3101001, value = 33

再來，則取出對應的所屬3101002，再次呼叫method，判斷是否有對應的數字

得到3101002對應數字已存在=> 33

回傳後，h2num.put(k, calHierarchy(k));  //k = 3101002, value = 33

跳出迴圈

回傳sum的總和 => 33 + 33 = 66，h2num.put(k, calHierarchy(k));  //k = 3101, value = 66

再來，則取出對應的所屬3102，再次呼叫method，判斷是否有對應的數字

若否，則取出對應的所屬3102001，再次呼叫method，判斷是否有對應的數字

得到3102001對應數字已存在=> 12

回傳後，h2num.put(k, calHierarchy(k));  //k = 3102001, value = 12

再來，則取出對應的所屬3102002，再次呼叫method，判斷是否有對應的數字

得到3102002對應數字已存在=> 31

回傳後，h2num.put(k, calHierarchy(k));  //k = 3102002, value = 31

跳出迴圈

回傳sum的總和 => 12 + 31 = 43，h2num.put(k, calHierarchy(k));  //k = 3102, value = 43

跳出迴圈

回傳sum的總和 => 66 + 43 = 109，h2num.put(k, calHierarchy(k));  //k = 31, value = 109

接下來，回到main method

由3101進入calHierarchy，3101對應數字已存在=66，回傳

由3101001進入calHierarchy，3101001對應數字已存在=33，回傳

由3102進入calHierarchy，3102對應數字已存在=43，回傳

由於，一開始在31進入後，已計算出接下來的3101、3101001等，因此後面的部分數字

都已經存在了!

最後，印出結果，得到所有代號對應的數字做結!