场景
- 背景
数据库中有一张存储树结构的表，表中有子节点（childId）和父节点（parentId）对应关系的字段。表中存储多棵树的数据，每棵树的根节点（rootId）的特点是：childId与parentId相等。数据如下图：
Paste_Image.png
- 需求
表中每棵树都可能有多级分支及多个叶子节点，需要定位出表中所有节点归属的树的根节点Id，放入map中(此处为java实现)，map的结构为map<childId,rootId>。最终结果如下图：
Paste_Image.png
思路
将表数据拼接取出，然后将数据转换为两个数组，一个是父节点数组、一个是子节点数组，同时，提取出表中的根节点数据。
然后，对子节点数组进行遍历，依据已经确定的根节点，递归查找出每个子节点的根，当子节点数据遍历完成，则所有数据定位完成。
实现代码
从数据库获取表数据，拼接成“childId,parentId”字符串。可以通过jdbc从查询表，获取resultSet，遍历resultSet进行拼接，比较简单，所以未编写代码。
/**
* 多树表，递归定位所有分支及叶子的根
* @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);
}
