title: java递归和反向递归

第一种，递归查询数据库结构，

第二种，一次性将数据库表中的所有数据查出来，然后再递归查出来的list集合，
第一种做法适合数据量较少的tree结构，因为要一直查询数据库数据量大时速度回相对较慢，所以数据量大时建议使用第二种方法，如图1所示是一个常见的树tree结构。图如下：

大家有么有遇到过这个问题：我想要根据关键字过滤查询出相关数据和它的上级结构，得到图1所示结果，可往往不知道怎么做，查不出上级结构总是得到图3类似的结构，要解决这个比较常见的问题就要用到反向递归的算法，网上我那个网搜不到类似的解决方案，本人一时兴趣来了，做了一套递归和反递归的解决方案，简单易懂，大家可以相互交流一下，图如下：

  1. /** 
  2. * 说明方法描述：将list转为树tree结构 
  3. *  
  4. * @param allRrecords 
  5. * @return 
  6. * @time 2016年5月10日 下午6:00:35 
  7. * @author yangdong 
  8. */  
  9.public List<Record> useListRecordToTree(List<Record> allRrecords) {  
  10.   
  11.List<Record> listParentRecord = new ArrayList<Record>();  
  12.List<Record> listNotParentRecord = new ArrayList<Record>();  
  13.// 第一步：遍历allRrecords保存所有数据的uuid用于判断是不是根节点  
  14.Map<String, String> mapAllUuid = new HashMap<String, String>();  
  15.Map<String, Record> allRecordMap = new HashMap<String, Record>();  
  16.for (Record record : allRrecords) {  
  17.mapAllUuid.put(record.getStr("uuid"), record.getStr("uuid"));  
  18.allRecordMap.put(record.getStr("uuid"), record);  
  19.}  
  20.// 第二步：遍历allRrecords找出所有的根节点和非根节点  
  21.if (allRrecords != null && allRrecords.size() > 0) {  
  22.for (Record record : allRrecords) {  
  23.if (StringUtil.isBlank(record.getStr("parent_uuid"))  
  24.|| !mapAllUuid.containsKey(record.getStr("parent_uuid"))) {  
  25.listParentRecord.add(record);  
  26.} else {  
  27.listNotParentRecord.add(record);  
  28.}  
  29.}  
  30.}  
  31.   
  32.// 第三步： 递归获取所有子节点  
  33.if (listParentRecord.size() > 0) {  
  34.for (Record record : listParentRecord) {  
  35.// 添加所有子级  
  36.record.set("childs", this.getTreeChildRecord(listNotParentRecord, record.getStr("uuid")));  
  37.}  
  38.}  
  39.return listParentRecord;  
  40.}  
  41.   
  42./** 
  43. * 说明方法描述：使list转换为树并根据关键字和节点名称过滤 
  44. *  
  45. * @param allRecords 所有节点 
  46. * @param keywords 要过滤的关键字 
  47. * @param filterFields 要过滤的字段 
  48. * @return 
  49. * @time 2016年5月19日 下午3:27:32 
  50. * @author yangdong 
  51. */  
  52.public List<Record> useListRecordToTreeByKeywords(List<Record> allRecords, String keywords, String... filterFields) {  
  53.List<Record> listRecord = new ArrayList<Record>();  
  54.Map<String, Record> allRecordMap = new HashMap<String, Record>();  
  55.for (Record record : allRecords) {  
  56.allRecordMap.put(record.getStr("uuid"), record);  
  57.}  
  58.// 遍历allRrecords找出所有的nodeName和关键字keywords相关的数据  
  59.if (allRecords != null && allRecords.size() > 0) {  
  60.if (filterFields.length > 1) {  
  61.for (Record record : allRecords) {  
  62.for (String field : filterFields) {  
  63.// 比较  
  64.if (record.getStr(field).toLowerCase().indexOf(keywords.toLowerCase()) != -1) {  
  65.listRecord.add(record);  
  66.}  
  67.}  
  68.}  
  69.} else {  
  70.for (Record record : allRecords) {  
  71.// 比较  
  72.if (record.getStr(filterFields[0]).toLowerCase().indexOf(keywords.toLowerCase()) != -1) {  
  73.listRecord.add(record);  
  74.}  
  75.}  
  76.}  
  77.}  
  78.// 查找过滤出来的节点和他们的父节点  
  79.listRecord = this.getSelfAndTheirParentRecord(listRecord, new ArrayList<Record>(),  
  80.  new HashMap<String, Record>(), allRecordMap);  
  81.// 将过滤出来的数据变成树tree结构  
  82.listRecord = this.useListRecordToTree(listRecord);  
  83.return listRecord;  
  84.}  
  85.   
  86./** 
  87. * 说明方法描述：递归查询子节点 
  88. *  
  89. * @param childList 子节点 
  90. * @param parentUuid 父节点id 
  91. * @return 
  92. * @time 2016年5月10日 下午3:29:35 
  93. * @author yangdong 
  94. */  
  95.private List<Record> getTreeChildRecord(List<Record> childList, String parentUuid) {  
  96.List<Record> listParentRecord = new ArrayList<Record>();  
  97.List<Record> listNotParentRecord = new ArrayList<Record>();  
  98.// 遍历tmpList，找出所有的根节点和非根节点  
  99.if (childList != null && childList.size() > 0) {  
  100.for (Record record : childList) {  
  101.// 对比找出父节点  
  102.if (StringUtil.equals(record.getStr("parent_uuid"), parentUuid)) {  
  103.listParentRecord.add(record);  
  104.} else {  
  105.listNotParentRecord.add(record);  
  106.}  
  107.   
  108.}  
  109.}  
  110.// 查询子节点  
  111.if (listParentRecord.size() > 0) {  
  112.for (Record record : listParentRecord) {  
  113.// 递归查询子节点  
  114.record.set("childs", getTreeChildRecord(listNotParentRecord, record.getStr("uuid")));  
  115.}  
  116.}  
  117.return listParentRecord;  
  118.}  
  119.   
  120./** 
  121. * 说明方法描述：递归找出本节点和他们的父节点 
  122. *  
  123. * @param parentList 根据关键字过滤出来的相关节点的父节点 
  124. * @param resultList 返回的过滤出来的节点 
  125. * @param filterRecordMap 已经过滤出来的节点 
  126. * @param allRecordMap 所有节点 
  127. * @return 
  128. * @time 2016年5月19日 上午9:53:56 
  129. * @author yangdong 
  130. */  
  131.private List<Record> getSelfAndTheirParentRecord(List<Record> parentList, List<Record> resultList,  
  132. Map<String, Record> filterRecordMap,  
  133. Map<String, Record> allRecordMap) {  
  134.// 当父节点为null或者节点数量为0时返回结果，退出递归  
  135.if (parentList == null || parentList.size() == 0) {  
  136.return resultList;  
  137.}  
  138.// 重新创建父节点集合  
  139.List<Record> listParentRecord = new ArrayList<Record>();  
  140.// 遍历已经过滤出来的节点  
  141.for (Record record : parentList) {  
  142.   
  143.String uuid = record.getStr("uuid");  
  144.String parent_uuid = record.getStr("parent_uuid");  
  145.   
  146.// 如果已经过滤出来的节点不存在则添加到list中  
  147.if (!filterRecordMap.containsKey(uuid)) {  
  148.listParentRecord.add(record);// 添加到父节点中  
  149.filterRecordMap.put(uuid, record);// 添加到已过滤的map中  
  150.allRecordMap.remove(uuid);// 移除集合中相应的元素  
  151.resultList.add(record);// 添加到结果集中  
  152.}  
  153.   
  154.// 找出本节点的父节点并添加到listParentRecord父节点集合中，并移除集合中相应的元素  
  155.if (StringUtil.isNotBlank(parent_uuid)) {  
  156.Record parentRecord = allRecordMap.get(parent_uuid);  
  157.if (parentRecord != null) {  
  158.listParentRecord.add(parentRecord);  
  159.allRecordMap.remove(parent_uuid);  
  160.}  
  161.}  
  162.   
  163.}  
  164.// 递归调用  
  165.getSelfAndTheirParentRecord(listParentRecord, resultList, filterRecordMap, allRecordMap);  
  166.   
  167.return resultList;  
  168.}  

/** 
 * 说明方法描述：递归查询所有权限 
 *  
 * @param keyword 
 * @param is_deleted 
 * @return 
 * @time 2016年5月10日 下午3:47:50 
 * @author yangdong 
 */  
public List<Record> getRecordByKeywordRecursive(String keyword, String is_deleted) {  
// 第一步：查询所有的数据  
StringBuffer sql = new StringBuffer(  
" select pa.uuid,pa.parent_uuid,pa.author_code,pa.author_name,pa.is_menu,pa.sort_number,pa.is_enable,pa.menu_icon ");  
sql.append("  from s_author pa");  
List<Object> params = new ArrayList<Object>();  
sql.append(" where  pa.is_deleted=? ");  
params.add(is_deleted);  
sql.append(" order by pa.sort_number asc ");  


List<Record> allRrecords = Db.use(AppConst.DB_DATASOURCE_MAIN).find(sql.toString(), ParamUtil.listToArray(params));  


//第二步：将list变为树tree结构  
if (StringUtil.isNotBlank(keyword)) {  
return super.useListRecordToTreeByKeywords(allRrecords, keyword, "author_name");  
} else {  
return super.useListRecordToTree(allRrecords);  
}  
}