java怎么用递归返回树结构的结果?

作者站长头像
站长
· 阅读数 3

一、想要实现的效果

- 以搜索“秦朗为例”,最后返回的是 三国-曹操-秦朗 的一条链路(一棵树)。

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;
}

三、代码执行结果java怎么用递归返回树结构的结果?

四、解释我递归用的少,用起来有点不达意。上面自己写的递归方法虽然能实现递归效果,但问题很大。4.1、我的方法返回的只是命中项,而不是一个树的结构(除非第一层就命中了)。4.2、返回的树里没有剔除未命中项。

上述两点(4.1和4.2)能否同时做到?如果不能,请指教怎么实现4.1,感谢。

回复
1个回答
avatar
test
2024-06-25
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":"三国"}]
    }
}
回复
likes
适合作为回答的
  • 经过验证的有效解决办法
  • 自己的经验指引,对解决问题有帮助
  • 遵循 Markdown 语法排版,代码语义正确
不该作为回答的
  • 询问内容细节或回复楼层
  • 与题目无关的内容
  • “赞”“顶”“同问”“看手册”“解决了没”等毫无意义的内容