正文

java递归和反向递归

IP云
IP云V管理员/7 阅读
06/27
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

1. 递归查询树tree结构有两种做法：

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

第二种，一次性将数据库表中的所有数据查出来，然后再递归查出来的list集合，

第一种做法适合数据量较少的tree结构，因为要一直查询数据库数据量大时速度回相对较慢，所以数据量大时建议使用第二种方法，如图1所示是一个常见的树tree结构

图1

2. 反向递归（逆向递归）查询树tree结构根据关键字过滤数据

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

图2

图3

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