java怎么用递归返回树结构的结果？
一、想要实现的效果
- 以搜索“秦朗为例”，最后返回的是 三国-曹操-秦朗 的一条链路（一棵树）。
二、我的代码
public class People {
private List<People> children;private String name;
// 省略getter、setter方法
}
public static void main(String[] args) {
People sunce = new People(); sunce.setName("孙策");
People sunquan = new People();
sunquan.setName("孙权");
People sunjian = new People();
sunjian.setName("孙坚");
sunjian.setChildren(Arrays.asList(sunce, sunquan));
People caopi = new People();
caopi.setName("曹丕");
People caozhi = new People();
caozhi.setName("曹植");
People caozhang = new People();
caozhang.setName("曹彰");
People qinlang = new People();
qinlang.setName("秦朗");
People caocao = new People();
caocao.setName("曹操");
caocao.setChildren(Arrays.asList(caopi, caozhi, caozhang, qinlang));
People liufeng = new People();
liufeng.setName("刘封");
People liushan = new People();
liushan.setName("刘禅");
People liubei = new People();
liubei.setName("刘备");
liubei.setChildren(Arrays.asList(liufeng, liushan));
People liuxun = new People();
liuxun.setName("刘循");
People liuzhang = new People();
liuzhang.setName("刘璋");
liuzhang.setChildren(Arrays.asList(liuxun));
People liuyan = new People();
liuyan.setName("刘焉");
liuyan.setChildren(Arrays.asList(liuzhang));
People sanguo = new People();
sanguo.setName("三国");
sanguo.setChildren(Arrays.asList(sunjian, caocao, liubei, liuyan));
List<People> p1 = query(sanguo, "刘");
System.out.println(p1);
List<People> p2 = query(sanguo, "秦");
System.out.println(p2);
List<People> p3 = query(sanguo, "孙策");
System.out.println(p3);
}
public static List<People> query(People people, String name) {
List<People> result = new ArrayList<>();
// 这里要判空，但简写就省略了
if(people.getName().contains(name)) {
return Arrays.asList(people);
} else {
if(people.getChildren() != null) {
for (People p : people.getChildren()) {
result.addAll(query(p, name));
}
}
}
return result;
}
三、代码执行结果
四、解释
我递归用的少，用起来有点不达意。上面自己写的递归方法虽然能实现递归效果，但问题很大。
4.1、我的方法返回的只是命中项，而不是一个树的结构（除非第一层就命中了）。
4.2、返回的树里没有剔除未命中项。
上述两点（4.1和4.2）能否同时做到？如果不能，请指教怎么实现4.1，感谢。
回答：
import com.alibaba.fastjson2.JSON;import lombok.Data;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
@Data
public class PeopleVO {
private Integer id;
private String peopleName;
private Integer parentId;
List<PeopleVO> children = new ArrayList<>();
//生成树
private static List<PeopleVO> createTree(List<PeopleVO> lists, int pid) {
List<PeopleVO> tree = new ArrayList<>();
for (PeopleVO people : lists) {
if (pid == people.getParentId()) {
tree.add(people);
}
}
for (PeopleVO people : tree) {
people.setChildren(createTree(lists, people.getId()));
}
return tree;
}
//从根节点出发到目标节点的路径，按列表顺序排列
private static List<PeopleVO> searchPeople(List<PeopleVO> tree, String name) {
List<PeopleVO> result = new ArrayList<>();
for (PeopleVO people : tree) {
if (people.getPeopleName().equals(name)) {
result.add(people);
return result;
}
List<PeopleVO> children = people.getChildren();
if (children != null && children.size() > 0) {
List<PeopleVO> searchResult = searchPeople(children, name);
if (searchResult.size() > 0) {
result.add(people);
result.addAll(searchResult);
return result;
}
}
}
return result;
}
//顺序组装节点,搜索结果方法已经是排好序的节点了
private static List<PeopleVO> createTree2(List<PeopleVO> nodeList) {
List<PeopleVO> tree = new ArrayList<>();
for (int i = 0; i <= nodeList.size() - 1; i++) {
PeopleVO node = nodeList.get(i);
PeopleVO sonNode = null;
if (i != nodeList.size() - 1) {
sonNode = nodeList.get(i + 1);
List<PeopleVO> nodeChildren = new ArrayList<>();
nodeChildren.add(sonNode);
node.setChildren(nodeChildren);
}else{
node.setChildren(null);
}
}
tree.add(nodeList.get(0));
return tree;
}
public static void main(String[] args) {
//三国
PeopleVO sanGuo = new PeopleVO();
sanGuo.setId(0);
sanGuo.setParentId(-1);
sanGuo.setPeopleName("三国");
//刘备
PeopleVO liuBei = new PeopleVO();
liuBei.setParentId(0);
liuBei.setId(1);
liuBei.setPeopleName("刘备");
//刘焉
PeopleVO liuYan = new PeopleVO();
liuYan.setParentId(0);
liuYan.setId(2);
liuYan.setPeopleName("刘焉");
//孙坚
PeopleVO sunJian = new PeopleVO();
sunJian.setParentId(0);
sunJian.setId(3);
sunJian.setPeopleName("孙坚");
//曹操
PeopleVO caoCao = new PeopleVO();
caoCao.setParentId(0);
caoCao.setId(4);
caoCao.setPeopleName("曹操");
//刘备的儿子们
//刘封
PeopleVO liuFeng = new PeopleVO();
liuFeng.setParentId(1);
liuFeng.setId(5);
liuFeng.setPeopleName("刘封");
//刘禅
PeopleVO liuShan = new PeopleVO();
liuShan.setParentId(1);
liuShan.setId(6);
liuShan.setPeopleName("刘禅");
//刘焉的儿子们
//刘璋
PeopleVO liuZhang = new PeopleVO();
liuZhang.setParentId(2);
liuZhang.setId(7);
liuZhang.setPeopleName("刘璋");
//刘循是刘璋的儿子
PeopleVO liuXun = new PeopleVO();
liuXun.setParentId(7);
liuXun.setId(8);
liuXun.setPeopleName("刘循");
//孙坚的儿子们
//孙策
PeopleVO sunCe = new PeopleVO();
sunCe.setParentId(3);
sunCe.setId(9);
sunCe.setPeopleName("孙策");
//孙权
PeopleVO sunQuan = new PeopleVO();
sunQuan.setParentId(3);
sunQuan.setId(10);
sunQuan.setPeopleName("孙权");
//曹操的儿子们
//曹丕
PeopleVO caoPi = new PeopleVO();
caoPi.setParentId(4);
caoPi.setId(11);
caoPi.setPeopleName("曹丕");
//曹植
PeopleVO caoZhi = new PeopleVO();
caoZhi.setParentId(4);
caoZhi.setId(12);
caoZhi.setPeopleName("曹植");
//曹彰
PeopleVO caoZhang = new PeopleVO();
caoZhang.setParentId(4);
caoZhang.setId(13);
caoZhang.setPeopleName("曹彰");
//秦朗
PeopleVO qinLang = new PeopleVO();
qinLang.setParentId(4);
qinLang.setId(14);
qinLang.setPeopleName("秦朗");
//每个人都添加自己的儿子列表
sanGuo.setChildren(Arrays.asList(liuBei, liuYan, sunJian, caoCao));
liuBei.setChildren(Arrays.asList(liuFeng, liuShan));
liuYan.setChildren(Collections.singletonList(liuZhang));
liuZhang.setChildren(Collections.singletonList(liuXun));
sunJian.setChildren(Arrays.asList(sunCe, sunQuan));
caoCao.setChildren(Arrays.asList(caoPi, caoZhi, caoZhang, qinLang));
//将所有人添加到一个集合中
List<PeopleVO> totalList = new ArrayList<>(Arrays.asList(sanGuo, liuBei, liuYan, sunJian, caoCao, liuFeng, liuShan, liuZhang, liuXun, sunCe, sunQuan, caoPi, caoZhi, caoZhang, qinLang));
//调用方法生成树
List<PeopleVO> tree = createTree(totalList, -1);
//调用方法搜索
List<PeopleVO> searchResult = searchPeople(tree, "孙坚");
List<PeopleVO> resultTree = createTree2(searchResult);
System.out.println(JSON.toJSONString(resultTree));
//秦朗的
//[{"children":[{"children":[{"id":14,"parentId":4,"peopleName":"秦朗"}],"id":4,"parentId":0,"peopleName":"曹操"}],"id":0,"parentId":-1,"peopleName":"三国"}]
//孙坚的
//[{"children":[{"id":3,"parentId":0,"peopleName":"孙坚"}],"id":0,"parentId":-1,"peopleName":"三国"}]
}
}
回答：
按你描述的需求来看，节点结构中只存放children可能不够，还需要加个parent，如下
public class People { // 父节点
private People parent;
private List<People> children;
private String name;
}
这样在递归查找出匹配的节点之后，因为每个节点都有parent和children，就能知道其完整的链路
以上是 java怎么用递归返回树结构的结果？ 的全部内容， 来源链接： utcz.com/p/945423.html
