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

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

对象中最重要的字段是子行数组定义结构，所有其他字段只是为了让开发人员理解节点的深度和结构(例如，深度包含每个父节点的索引加上当前节点的索引，全部用点分隔)。

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

每个对象都是一个Row对象，在前端所有的行创建一个表。以下Row.java模型类:

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