title: java递归和反向递归
tags: java
categories: java
archives: /archives
递归查询树tree结构有两种做法
第一种,递归查询数据库结构,
第二种,一次性将数据库表中的所有数据查出来,然后再递归查出来的list集合,
第一种做法适合数据量较少的tree结构,因为要一直查询数据库数据量大时速度回相对较慢,所以数据量大时建议使用第二种方法,如图1所示是一个常见的树tree结构。图如下:
反向递归(逆向递归)查询树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);
}
}
近期评论