場(chǎng)景
- 背景
數(shù)據(jù)庫中有一張存儲(chǔ)樹結(jié)構(gòu)的表战坤，表中有子節(jié)點(diǎn)（childId）和父節(jié)點(diǎn)（parentId）對(duì)應(yīng)關(guān)系的字段曙强。表中存儲(chǔ)多棵樹的數(shù)據(jù)，每棵樹的根節(jié)點(diǎn)（rootId）的特點(diǎn)是：childId與parentId相等途茫。數(shù)據(jù)如下圖：
Paste_Image.png
- 需求
表中每棵樹都可能有多級(jí)分支及多個(gè)葉子節(jié)點(diǎn)碟嘴，需要定位出表中所有節(jié)點(diǎn)歸屬的樹的根節(jié)點(diǎn)Id，放入map中(此處為java實(shí)現(xiàn))囊卜，map的結(jié)構(gòu)為map<childId,rootId>臀防。最終結(jié)果如下圖：
Paste_Image.png
思路
將表數(shù)據(jù)拼接取出眠菇，然后將數(shù)據(jù)轉(zhuǎn)換為兩個(gè)數(shù)組，一個(gè)是父節(jié)點(diǎn)數(shù)組袱衷、一個(gè)是子節(jié)點(diǎn)數(shù)組捎废，同時(shí)，提取出表中的根節(jié)點(diǎn)數(shù)據(jù)致燥。
然后登疗，對(duì)子節(jié)點(diǎn)數(shù)組進(jìn)行遍歷，依據(jù)已經(jīng)確定的根節(jié)點(diǎn)嫌蚤，遞歸查找出每個(gè)子節(jié)點(diǎn)的根辐益，當(dāng)子節(jié)點(diǎn)數(shù)據(jù)遍歷完成，則所有數(shù)據(jù)定位完成脱吱。
實(shí)現(xiàn)代碼
從數(shù)據(jù)庫獲取表數(shù)據(jù)智政，拼接成“childId,parentId”字符串∠潋穑可以通過jdbc從查詢表续捂，獲取resultSet，遍歷resultSet進(jìn)行拼接宦搬，比較簡(jiǎn)單牙瓢，所以未編寫代碼。
/**
* 多樹表间校，遞歸定位所有分支及葉子的根
* @param child_parent_list
* @author 張文健
* @return
*/
public static Map<String,String> rootMap(List<String> child_parent_list){
Map<String,String> child_parent_map = new HashMap<String,String>();
String[] parentArr = new String[child_parent_list.size()];
String[] childArr = new String[child_parent_list.size()];
for(int i=0;i<child_parent_list.size();i++){
String ic = child_parent_list.get(i).split(",")[0];
String ip = child_parent_list.get(i).split(",")[1];
parentArr[i] = ip;
childArr[i] = ic;
if(ic.equals(ip)){
child_parent_map.put(ip, ip);
}
}
goods: for(int i=0;i<childArr.length;i++){
String finder = parentArr[i];
machine: for(int j=0;j<childArr.length;j++){
if(finder.equals(childArr[j])){
if(child_parent_map.containsValue(childArr[j])){
child_parent_map.put(childArr[i], childArr[j]);
continue goods;
}else{
finder = parentArr[j];
j=0;
continue machine;
}
}
}
}
return child_parent_map;
}
public static void main(String[] args) {
List<String> child_parent_list = new ArrayList<String>();
child_parent_list.add("000087,000086");
child_parent_list.add("000088,000086");
child_parent_list.add("000105,000088");
child_parent_list.add("000106,000105");
child_parent_list.add("000086,000086");
child_parent_list.add("000091,000091");
child_parent_list.add("000092,000091");
child_parent_list.add("000093,000091");
child_parent_list.add("000096,000096");
child_parent_list.add("000097,000096");
child_parent_list.add("000098,000096");
child_parent_list.add("000099,000096");
child_parent_list.add("000113,000111");
child_parent_list.add("000112,000111");
child_parent_list.add("000114,000111");
child_parent_list.add("000111,000111");
ServiceUtil.rootMap(child_parent_list);
}
