将平面列表转换为具有每个节点深度的树结构

Question

我正在使用 java，我需要将平面 Set<Object> 转换为一组对象，它可以递归地包含其他对象列表。

我从 React 前端收到这个 JSON 数据：

[
    {
        name : "A",
        depth: "0",
        fullpath: "/A",
        subRows: null
    },
    {
        name : "B",
        depth: "0.0",
        fullPath: "/A/B"
        subRows: null
    },
    {
        name : "C",
        depth: "0.0.0",
        fullPath: "/A/B/C",
        subRows: null
    },
    {
        name : "D",
        depth: "1,
        fullPath: "/D",
        subRows: null
    }
]

我想把它转换成这个结构（相同的数据，但有父子关系）：

[
    {
        name : "A",
        depth: "0",
        fullPath: "/A",
        subRows: [
            {
                name : "B",
                depth: "0.0",
                fullPath: "/A/B",
                subRows: [
                    {
                        name : "C",
                        depth: "0.0.0",
                        fullPath: "/A/B/C",
                        subRows: null
                    }
                ]
            }           
        ]
    }
    {
        name : "D",
        depth: "1,
        fullPath: "/D",
        subRows: null;
    }   
]

对象中最重要的字段是定义结构的subRows数组，所有其他字段仅供开发人员了解节点的深度和结构（例如，Depth 包含每个父节点的索引加上当前节点的索引，均以点分隔）。

请不要过分依赖 fullPath，因为对象的名称不是唯一的。

这些对象中的每一个都是一个 Row 对象，在前端所有的行创建一个 table。关注 Row.java 型号 class:

public class Row {

    @Id
    @GeneratedValue(strategy = GenerationType.AUTO)
    private int id;


    private String name;
    private String depth;
    private String fullPath;
    
    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name="ID_PARENT")
    @JsonIgnore
    private Row parent;

    @OneToMany(mappedBy="parent", fetch = FetchType.EAGER)
    @org.hibernate.annotations.OrderBy(clause = "id")
    private Set<Row> subRows = new LinkedHashSet<Row>();
    
    public Row(){}
    
    //Getter and Setter
}

有人知道怎么做吗？这几天我一直在苦苦思索。

Answer 1

下面是执行上述任务的 sudo 代码。您可能需要处理一些极端情况。但主要思想是维护 pendingRows 的列表。对于此列表中的每一行，如果父节点已存在于 depthToRows 映射中，我们将将该行插入到父节点的子行中并从 pendingRows 中删除该行。我们需要重复此操作，直到 pendingRows 为空。

        List<Row> inRows; //input to the algo
        List<Row> pendingRows = new LinkedList<>();
        Map<String, Row> depthToRows = new HashMap<>();

        pendingRows.addAll(inRows);
        while (!pendingRows.isEmpty()){
            for(Row row: inRows){
                depthToRows.put(row.getDepth(), row);
                //find the parent depth object
                String[] arr = row.getDepth().split(".");
                if(arr.length > 1){
                    String parentDepth = String.join(".", Arrays.copyOfRange(arr, 0, arr.length - 1));
                    if(null != depthToRows.get(parentDepth)){
                        depthToRows.get(parentDepth).getSubRows().add(row);
                        pendingRows.remove(row);
                    }
                }
            }
        }

将平面列表转换为具有每个节点深度的树结构

Convert a flat list into tree structure having the depth of each node

java

recursion

nested-loops