多树表，递归查找所有分支及叶子的根

场景

• 背景
  数据库中有一张存储树结构的表，表中有子节点（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);
}