• JAVA将List转成Tree树形结构数据和深度优先遍历

    引言：

    在日常开发中，我们经常会遇到需要将数据库中返回的数据转成树形结构的数据返回，或者需要对转为树结构后的数据绑定层级关系再返回，比如需要统计当前节点下有多少个节点等，因此我们需要封装一个ListToTree的工具类和学会如何通过深度优先遍历数据。

    数据准备：

    先简单准备一下具有父子关系的数据。

    1. package data;
    2.  
    3.  
    4. /**
    5. * @author sinder
    6. * @date 2023/11/8 21:40
    7. */
    8. public class OrgData {
    9.     private String id;
    10.  
    11.     private String pId;
    12.  
    13.     private String orgName;
    14.  
    15.     public String getId() {
    16.         return id;
    17.     }
    18.  
    19.     public void setId(String id) {
    20.         this.id = id;
    21.     }
    22.  
    23.     public String getpId() {
    24.         return pId;
    25.     }
    26.  
    27.     public void setpId(String pId) {
    28.         this.pId = pId;
    29.     }
    30.  
    31.     public String getOrgName() {
    32.         return orgName;
    33.     }
    34.  
    35.     public void setOrgName(String orgName) {
    36.         this.orgName = orgName;
    37.     }
    38. }
    1. package data;
    2.  
    3. import java.util.ArrayList;
    4. import java.util.List;
    5.  
    6. /**
    7.  * 生成数据，模拟数据库查询
    8.  * @author sinder
    9.  * @date 2023/11/8 22:17
    10.  */
    11. public class SingData {
    12.     public static List getData() {
    13.         OrgData orgData1 = new OrgData();
    14.         orgData1.setId("1");
    15.         orgData1.setpId("root");
    16.         orgData1.setOrgName("根节点A");
    17.  
    18.         OrgData orgData2 = new OrgData();
    19.         orgData2.setId("2");
    20.         orgData2.setpId("root");
    21.         orgData2.setOrgName("根节点B");
    22.  
    23.         OrgData orgData3 = new OrgData();
    24.         orgData3.setId("3");
    25.         orgData3.setpId("1");
    26.         orgData3.setOrgName("A目录");
    27.  
    28.         OrgData orgData4 = new OrgData();
    29.         orgData4.setId("4");
    30.         orgData4.setpId("2");
    31.         orgData4.setOrgName("B目录");
    32.  
    33.         List list = new ArrayList<>();
    34.         list.add(orgData1);
    35.         list.add(orgData2);
    36.         list.add(orgData3);
    37.         list.add(orgData4);
    38.  
    39.         return list;
    40.     }
    41. }

    正常情况下，我们都会选择封装一个将List转换为Tree的工具类，并且通过链式顺序LinkedList存储来遍历Tree数据，这里使用stream来实现，如下：

    1. package data;
    2.  
    3. import java.util.List;
    4.  
    5. /**
    6.  * 构建tree数据
    7.  * @author sinder
    8.  * @date 2023/11/8 22:30
    9.  */
    10. public class TreeBean {
    11.     private String treeId;
    12.  
    13.     private String treePid;
    14.  
    15.     private String orgName;
    16.  
    17.     private Integer flag = 0;
    18.  
    19.     private List children;
    20.  
    21.     private OrgData orgData;
    22.  
    23.     public String getTreeId() {
    24.         return treeId;
    25.     }
    26.  
    27.     public void setTreeId(String treeId) {
    28.         this.treeId = treeId;
    29.     }
    30.  
    31.     public String getOrgName() {
    32.         return orgName;
    33.     }
    34.  
    35.     public void setOrgName(String orgName) {
    36.         this.orgName = orgName;
    37.     }
    38.  
    39.     public String getTreePid() {
    40.         return treePid;
    41.     }
    42.  
    43.     public void setTreePid(String treePid) {
    44.         this.treePid = treePid;
    45.     }
    46.  
    47.     public List getChildren() {
    48.         return children;
    49.     }
    50.  
    51.     public void setChildren(List children) {
    52.         this.children = children;
    53.     }
    54.  
    55.     public OrgData getOrgData() {
    56.         return orgData;
    57.     }
    58.  
    59.     public void setOrgData(OrgData orgData) {
    60.         this.orgData = orgData;
    61.     }
    62.  
    63.     public Integer getFlag() {
    64.         return flag;
    65.     }
    66.  
    67.     public void setFlag(Integer flag) {
    68.         this.flag = flag;
    69.     }
    70.  
    71.     @Override
    72.     public String toString() {
    73.         return "TreeBean{" +
    74.                 "treeId='" + treeId + '\'' +
    75.                 ", treePid='" + treePid + '\'' +
    76.                 ", orgName='" + orgName + '\'' +
    77.                 ", children=" + children +
    78.                 '}';
    79.     }
    80. }
    1. package utils;
    2.  
    3. import data.OrgData;
    4. import data.SingData;
    5. import data.TreeBean;
    6.  
    7. import java.util.ArrayList;
    8. import java.util.List;
    9. import java.util.Map;
    10. import java.util.Objects;
    11. import java.util.stream.Collectors;
    12.  
    13. /**
    14.  * 将List转为Tree
    15.  *
    16.  * @author sinder
    17.  * @date 2023/11/8 22:28
    18.  */
    19. public class ListToTreeUtil {
    20.     public static List toTree(List list, String root) {
    21.         if (list.isEmpty()) {
    22.             return new ArrayList<>();
    23.         }
    24.         // 构建数据
    25.         List treeBeans = list.stream().map(item -> {
    26.             TreeBean treeBean = new TreeBean();
    27.             treeBean.setTreeId(item.getId());
    28.             treeBean.setTreePid(item.getpId());
    29.             treeBean.setOrgName(item.getOrgName());
    30.             return treeBean;
    31.         }).collect(Collectors.toList());
    32.  
    33.         // 构建Map数据
    34.         Map> treeMap = treeBeans.stream().collect(Collectors.groupingBy(item -> {
    35.             if (item.getTreePid().isEmpty()) {
    36.                 item.setTreePid(root);
    37.             }
    38.             return item.getTreePid();
    39.         }));
    40.  
    41.         // 将数据进行分组
    42.         return treeBeans.stream().peek(data -> {
    43.             List children = treeMap.get(data.getTreeId());
    44.             if (children != null && !children.isEmpty()) {
    45.                 data.setChildren(children);
    46.             }
    47.         }).filter(data -> data.getTreePid().equals(root)).collect(Collectors.toList());
    48.     }
    49. }

    执行结果：

    620fc2d13f944d61888c2f0af8198ad2.png

    对tree数据进行遍历，通过链表的形式：

    1. import data.OrgData;
    2. import data.SingData;
    3. import data.TreeBean;
    4. import utils.ListToTreeUtil;
    5.  
    6. import java.util.LinkedList;
    7. import java.util.List;
    8. import java.util.stream.Collectors;
    9.  
    10. /**
    11.  * @author sinder
    12.  * @date 2023/11/8 20:44
    13.  */
    14. public class Main {
    15.     public static void main(String[] args) {
    16.         // 模拟查询数据
    17.         List orgDataList = SingData.getData();
    18.         // 构建tree数据
    19.         List treeBean = ListToTreeUtil.toTree(orgDataList, "root");
    20.         // 使用LinkedList实现链式队列，实现深度遍历
    21.         LinkedList stack = new LinkedList<>();
    22.         stack.addAll(treeBean);
    23.         while (!stack.isEmpty()) {
    24.             // 从栈顶开始访问
    25.             TreeBean pop = stack.peek();
    26.             // Flag=1表示已经遍历过一次且该节点存在子节点
    27.             if (pop.getFlag() == 1) {
    28.                 OrgData orgData =pop.getOrgData();
    29.                 List children = pop.getChildren();
    30.                 // 获取子节点的节点名称，也可以进行其他的操作
    31.                 List collect = children.stream().map(TreeBean::getOrgName).collect(Collectors.toList());
    32.                 StringBuilder builder = new StringBuilder();
    33.                 for (String s : collect) {
    34.                     builder.append(s);
    35.                     builder.append(">");
    36.                 }
    37.                 pop.setOrgName(builder.toString());
    38.                 orgData.setOrgName(pop.getOrgName());
    39.                 // pop出栈，当前节点已经统计完，出栈获取下一个栈顶peek
    40.                 stack.pop();
    41.             } else {
    42.                 // flag为0表示未遍历，判断是否已经遍历到叶子节点(最底部)
    43.                 if (pop.getChildren()!= null && !pop.getChildren().isEmpty()) {
    44.                     // 非叶子节点
    45.                     pop.setFlag(1);
    46.                     List children = pop.getChildren();
    47.                     for (TreeBean child : children) {
    48.                         // 将叶子节点入栈，放到栈顶，实现深度遍历，next
    49.                         stack.push(child);
    50.                     }
    51.                 } else {
    52.                     // 叶子节点直接出栈即可，cnt为本身
    53.                     stack.pop();
    54.                 }
    55.             }
    56.         }
    57.  
    58.         // 遍历最终的数据
    59.         for (OrgData orgData : orgDataList) {
    60.             System.out.println(orgData.toString());
    61.         }
    62.     }
    63. }

    1295308cbbed42f1a1e5d461a1056e2c.png

    但是现在有一个问题，当我们响应的数据从OrgData换到其他类型的时候，这时候就需要封装成一个泛型类使得我们的tree数据生成类变成一个通用的，完整代码如下：

    完整代码：JAVA将List转为Tree和深度优先遍历

    1. package data;
    2.  
    3. import java.util.List;
    4.  
    5. /**
    6.  * 定义一个接口，使得每一个响应的数据实体来实现
    7.  * @author sinder
    8.  * @date 2023/11/9 0:31
    9.  */
    10. public interface Tree {
    11.     String getTreeId();
    12.  
    13.     String getTreePid();
    14.  
    15.     void setChild(List list);
    16. }
    1. package data;
    2.  
    3.  
    4. import java.util.List;
    5.  
    6. /**
    7.  * 实现Tree并定义响应类型为本身
    8.  * 定义转为树的参数返回
    9. * @author sinder
    10. * @date 2023/11/8 21:40
    11. */
    12. public class OrgData implements Tree{
    13.     private String id;
    14.  
    15.     private String pId;
    16.  
    17.     private String orgName;
    18.  
    19.     // 转成树需要的参数
    20.     private Integer flag = 0;
    21.  
    22.     private List child;
    23.  
    24.     public String getId() {
    25.         return id;
    26.     }
    27.  
    28.     public void setId(String id) {
    29.         this.id = id;
    30.     }
    31.  
    32.     public String getpId() {
    33.         return pId;
    34.     }
    35.  
    36.     public void setpId(String pId) {
    37.         this.pId = pId;
    38.     }
    39.  
    40.     public String getOrgName() {
    41.         return orgName;
    42.     }
    43.  
    44.     public void setOrgName(String orgName) {
    45.         this.orgName = orgName;
    46.     }
    47.  
    48.     public Integer getFlag() {
    49.         return flag;
    50.     }
    51.  
    52.     public void setFlag(Integer flag) {
    53.         this.flag = flag;
    54.     }
    55.  
    56.     public List getChild() {
    57.         return child;
    58.     }
    59.  
    60.     @Override
    61.     public String toString() {
    62.         return "OrgData{" +
    63.                 "id='" + id + '\'' +
    64.                 ", pId='" + pId + '\'' +
    65.                 ", orgName='" + orgName + '\'' +
    66.                 '}';
    67.     }
    68.  
    69.     @Override
    70.     public String getTreeId() {
    71.         return id;
    72.     }
    73.  
    74.     @Override
    75.     public String getTreePid() {
    76.         return pId;
    77.     }
    78.  
    79.     @Override
    80.     public void setChild(List list) {
    81.         this.child = list;
    82.     }
    83. }

    ListToTree方法

    1. package utils;
    2.  
    3. import data.OrgData;
    4. import data.SingData;
    5. import data.Tree;
    6. import data.TreeBean;
    7.  
    8. import java.util.ArrayList;
    9. import java.util.List;
    10. import java.util.Map;
    11. import java.util.Objects;
    12. import java.util.stream.Collectors;
    13.  
    14. /**
    15.  * 将List转为Tree
    16.  * 告诉编译器有Tree的get方法
    17.  *
    18.  * @author sinder
    19.  * @date 2023/11/8 22:28
    20.  */
    21. public class ListToTreeUtil {
    22.     public static extends Tree> List toTree(List list, String root) {
    23.         // 当根节点为null时，定义一个初始值，防止null
    24.         String treeRoot = "treeRoot";
    25.         String finalRoot = root;
    26.         if (list.isEmpty()) {
    27.             return new ArrayList<>();
    28.         }
    29.  
    30.         // 构建Map数据
    31.         // 根据pid分组，获取所有的子节点集合
    32.         Map> childMap =
    33.                 list.stream()
    34.                         .collect(Collectors.groupingBy(item -> {
    35.                             String treePid = item.getTreePid();
    36.                             if (treePid == null) {
    37.                                 treePid = treeRoot;
    38.                             }
    39.                             return treePid;
    40.                         }));
    41.         return list.stream().peek(
    42.                 data -> {
    43.                     List children = childMap.get(data.getTreeId());
    44.                     if (children != null && !children.isEmpty()) {
    45.                         data.setChild(children);
    46.                     }
    47.                 })
    48.                 .filter(data -> data.getTreePid().equals(finalRoot))
    49.                 .collect(Collectors.toList());
    50.     }
    51. }

    深度优先遍历

    1. import data.OrgData;
    2. import data.SingData;
    3. import data.TreeBean;
    4. import utils.ListToTreeUtil;
    5.  
    6. import java.util.LinkedList;
    7. import java.util.List;
    8. import java.util.stream.Collectors;
    9.  
    10. /**
    11.  * @author sinder
    12.  * @date 2023/11/8 20:44
    13.  */
    14. public class Main {
    15.     public static void main(String[] args) {
    16.         // 模拟查询数据
    17.         List orgDataList = SingData.getData();
    18.         // 构建tree数据
    19.         List treeBean = ListToTreeUtil.toTree(orgDataList, "root");
    20.         // 使用LinkedList实现链式队列，实现深度遍历
    21.         LinkedList stack = new LinkedList<>();
    22.         stack.addAll(treeBean);
    23.         while (!stack.isEmpty()) {
    24.             // 从栈顶开始访问
    25.             OrgData pop = stack.peek();
    26.             // Flag=1表示已经遍历过一次且该节点存在子节点
    27.             if (pop.getFlag() == 1) {
    28.                 List children = pop.getChild();
    29.                 // 获取子节点的节点名称，也可以进行其他的操作
    30.                 List collect = children.stream().map(OrgData::getOrgName).collect(Collectors.toList());
    31.                 StringBuilder builder = new StringBuilder();
    32.                 for (String s : collect) {
    33.                     builder.append(s);
    34.                     builder.append(">");
    35.                 }
    36.                 pop.setOrgName(builder.toString());
    37.                 // pop出栈，当前节点已经统计完，出栈获取下一个栈顶peek
    38.                 stack.pop();
    39.             } else {
    40.                 // flag为0表示未遍历，判断是否已经遍历到叶子节点(最底部)
    41.                 if (pop.getChild()!= null && !pop.getChild().isEmpty()) {
    42.                     // 非叶子节点
    43.                     pop.setFlag(1);
    44.                     List children = pop.getChild();
    45.                     for (OrgData child : children) {
    46.                         // 将叶子节点入栈，放到栈顶，实现深度遍历，next
    47.                         stack.push(child);
    48.                     }
    49.                 } else {
    50.                     // 叶子节点直接出栈即可，cnt为本身
    51.                     stack.pop();
    52.                 }
    53.             }
    54.         }
    55.  
    56.         // 遍历最终的数据
    57.         for (OrgData orgData : orgDataList) {
    58.             System.out.println(orgData.toString());
    59.         }
    60.     }
    61. }

    7e6b1547ec5a47c0bc8b4d6f340fc78f.png

            文章主要讲了tree数据的生成策略和对tree数据的深度遍历，整体上先构建出一个tree数据，为了能兼容多Object数据转为tree之后的遍历，因此使用了泛型，并且定义了Tree接口，提供了getid、getPid、setChild等操作方法，实体类在实现了Tree接口后就可以使用相应的方法来操作父子关系相关的ip和pid以及子节点来构建相关的tree数据，这也方便的在使用LinkedList深度遍历tree能更加灵活的操作父子节点的数据，主要通过出栈入栈来实现深度遍历，一路从父节点一直遍历到叶子节点才停止。

    文章仅为参考示例，更多更好的实现方式欢迎留言评论呀！

     

     

  • 相关阅读:
    威马汽车欲曲线上市：沈晖已提前持股并任职，销量垫底、员工降薪
    dfs+剪枝，LeetCode 39. 组合总和
    向Zookeeper中注册内容以及从zookeeper中发现内容
    【宋红康 MySQL数据库 】【高级篇】【20】其他数据库日志
    MySQL支持哪些存储引擎
    计算机毕业设计Java餐厅点餐系统(源码+系统+mysql数据库+lw文档)
    大语言模型迎来重大突破！找到解释神经网络行为方法
    SVM & FC+Softmax 分类
    针对CSP-J/S的每日一练：Day7
    C++： using 关键字
  • 原文地址：https://blog.csdn.net/weixin_42009068/article/details/134299238