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

912051

发布于
2023-11-13 甘肃

更新于
2023-11-13

一、想要实现的效果

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

二、我的代码
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，感谢。

后端

java

阅读 932

AI BotBETA

这个问题可以通过使用递归和合适的数据结构来解决。在Java中，我们可以使用树结构（或者更具体地说，是树的列表）来存储每个人物及其子女的信息。然后，我们可以使用递归来查找从根节点到目标节点的路径。

为了实现你的需求，你可能需要对你的People类进行一些修改。尤其是，你需要为每个人物维护一个子节点列表，而不是仅仅为曹操和刘备。同时，你需要创建一个方法来构建这个树结构。以下是一个可能的实现：

import java.util.*;

public class People {
    private String name;
    private List<People> children;

    public People(String name) {
        this.name = name;
        this.children = new ArrayList<>();
    }

    public void addChild(People child) {
        this.children.add(child);
    }

    public String getName() {
        return this.name;
    }

    public List<People> getChildren() {
        return this.children;
    }
}

然后，你可以在main方法中创建树结构：

public static void main(String[] args) {
    // 创建节点
    People sunjian = new People("孙坚");
    People sunce = new People("孙策");
    People sunquan = new People("孙权");
    sunjian.addChild(sunce);
    sunjian.addChild(sunquan);

    People caocao = new People("曹操");
    People caopi = new People("曹丕");
    People caozhi = new People("曹植");
    People caozhang = new People("曹彰");
    caocao.addChild(caopi);
    caocao.addChild(caozhi);
    caocao.addChild(caozhang);
    caocao.addChild(qinlang); // 这里需要添加 qinlang 节点，但你的代码中没有提供创建它的方法，我在这里添加它以便下面的代码可以运行。

    // ... 其他节点创建方法类似，不再赘述。

    // 构建树结构
    People sanguo = new People("三国");
    sanguo.addChild(sunjian);
    sanguo.addChild(caocao);
    // ... 添加其他节点 ...
}

接下来，你可以使用递归方法来查找从根节点到目标节点的路径。以下是一个可能的实现：

public static List<People> query(People people, String name) {
    List<People> result = new ArrayList<>();
    if (people == null) {
        return result;
    } else if (people.getName().equals(name)) { // 找到目标节点，返回当前节点及其所有子节点（包括子节点的子节点等）
        result.add(people);
        result.addAll(people.getChildren()); // 包括当前节点的所有子节点。递归调用 query 方法，继续查找子节点的子节点。

2 个回答

得票最新

Undest

2.4k2517

发布于
2023-11-14 广东

更新于
2023-11-14

✓ 已被采纳

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":"三国"}]
    }
}

kamier

1.5k11022

发布于
2023-11-14 福建

按你描述的需求来看，节点结构中只存放children可能不够，还需要加个parent，如下

public class People {
    // 父节点
    private People parent;
    private List<People> children;
    private String name;
}

这样在递归查找出匹配的节点之后，因为每个节点都有parent和children，就能知道其完整的链路

撰写回答

你尚未登录，登录后可以

和开发者交流问题的细节
关注并接收问题和回答的更新提醒
参与内容的编辑和改进，让解决方法与时俱进

推荐问题

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

你尚未登录，登录后可以

小网站有必要将图片放到阿里云OSS存储吗？

Spring中的两个疑惑?

Qt中布局是否只有5种呢？

为什么在 aws 新开 ec2 机器不显示价格？

字节的 trae AI IDE 不支持类似 vscode 的 ssh remote 远程开发怎么办？

请问一下，如何理解reduce函数呢？

爬取知乎热榜数据，跳转链接从哪里爬取？