这里是一个 Ruby 的实现:
它可以按属性名或方法调用结果进行分类目录。
CatalogGenerator = ->(depth) do
if depth != 0
->(hash, key) do
hash[key] = Hash.new(&CatalogGenerator[depth - 1])
end
else
->(hash, key) do
hash[key] = []
end
end
end
def catalog(collection, root_name: :root, by:)
method_names = [*by]
log = Hash.new(&CatalogGenerator[method_names.length])
tree = collection.each_with_object(log) do |item, catalog|
path = method_names.map { |method_name| item.public_send(method_name)}.unshift(root_name.to_sym)
catalog.dig(*path) << item
end
tree.with_indifferent_access
end
students = [#<Student:0x007f891d0b4818 id: 33999, status: "on_hold", tenant_id: 95>,
#<Student:0x007f891d0b4570 id: 7635, status: "on_hold", tenant_id: 6>,
#<Student:0x007f891d0b42c8 id: 37220, status: "on_hold", tenant_id: 6>,
#<Student:0x007f891d0b4020 id: 3444, status: "ready_for_match", tenant_id: 15>,
#<Student:0x007f8931d5ab58 id: 25166, status: "in_partnership", tenant_id: 10>]
catalog students, by: [:tenant_id, :status]
# this would out put the following
{"root"=>
{95=>
{"on_hold"=>
[#<Student:0x007f891d0b4818
id: 33999,
status: "on_hold",
tenant_id: 95>]},
6=>
{"on_hold"=>
[#<Student:0x007f891d0b4570 id: 7635, status: "on_hold", tenant_id: 6>,
#<Student:0x007f891d0b42c8
id: 37220,
status: "on_hold",
tenant_id: 6>]},
15=>
{"ready_for_match"=>
[#<Student:0x007f891d0b4020
id: 3444,
status: "ready_for_match",
tenant_id: 15>]},
10=>
{"in_partnership"=>
[#<Student:0x007f8931d5ab58
id: 25166,
status: "in_partnership",
tenant_id: 10>]}}}
使用指针的Golang解决方案。由于每次迭代基本上都指向同一对象，导致N空间和时间复杂度。
https://go.dev/play/p/lrPBTawy7Su
func TestCommentTree(t *testing.T) {
var listRaw = `[{"id":5,"parentPostID":0,"parentID":null,"authorID":1,"content":"asadas","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":9,"parentPostID":0,"parentID":5,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":10,"parentPostID":0,"parentID":9,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":11,"parentPostID":0,"parentID":5,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":12,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":13,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":14,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":15,"parentPostID":0,"parentID":12,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":16,"parentPostID":0,"parentID":11,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":17,"parentPostID":0,"parentID":16,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":18,"parentPostID":0,"parentID":17,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":19,"parentPostID":0,"parentID":18,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"}]`
type Comment struct {
ID uint64 `db:"id" json:"id"`
ParentPostID uint64 `db:"parent_post_id" json:"parentPostID"`
ParentID *int `db:"parent_id" json:"parentID"` // allow nullable on lvl 0 comment
AuthorID uint64 `db:"author_id" json:"authorID"`
Content string `db:"content" json:"content"`
Replies []*Comment `json:"replies"`
CreatedAt time.Time `db:"created_at" json:"createdAt"`
UpdatedAt time.Time `db:"updated_at" json:"updatedAt"`
}
var c []*Comment
err := json.Unmarshal([]byte(listRaw), &c)
if err != nil {
panic(err)
}
node := make(map[uint64]*Comment)
for _, v := range c {
node[v.ID] = v
}
for _, comm := range node {
if comm.ParentID == nil {
continue
}
parent := node[uint64(*comm.ParentID)]
if parent == nil {
panic(fmt.Sprintf("parent nil %d", *comm.ParentID))
}
if parent.Replies == nil {
parent.Replies = make([]*Comment, 0)
parent.Replies = append(parent.Replies, comm)
} else {
parent.Replies = append(parent.Replies, comm)
}
}
res := make([]*Comment, 0)
for _, comm := range node {
if comm.ParentID != nil {
continue
}
res = append(res, comm)
}
s, _ := json.MarshalIndent(res, "", "\t")
fmt.Println(string(s))
}
我觉得被接受的答案过于复杂，所以我添加了Ruby和NodeJS版本的代码。
假设扁平节点列表具有以下结构：
nodes = [
{ id: 7, parent_id: 1 },
...
] # ruby
nodes = [
{ id: 7, parentId: 1 },
...
] # nodeJS
def to_tree(nodes)
nodes.each do |node|
parent = nodes.find { |another| another[:id] == node[:parent_id] }
next unless parent
node[:parent] = parent
parent[:children] ||= []
parent[:children] << node
end
nodes.select { |node| node[:parent].nil? }
end
对于 NodeJS：
const toTree = (nodes) => {
nodes.forEach((node) => {
const parent = nodes.find((another) => another.id == node.parentId)
if(parent == null) return;
node.parent = parent;
parent.children = parent.children || [];
parent.children = parent.children.concat(node);
});
return nodes.filter((node) => node.parent == null)
};
null == undefined => true。 - Hirurg103一种优雅的方法是将列表中的项表示为一个字符串，其中包含以点分隔的父项列表，最后是一个值：
server.port=90
server.hostname=localhost
client.serverport=90
client.database.port=1234
client.database.host=localhost
server:
port: 90
hostname: localhost
client:
serverport=1234
database:
port: 1234
host: localhost
虽然这个问题对我来说有些模糊，但我可能会创建一个从ID到实际对象的映射。在伪Java中（我没有检查它是否可以工作/编译），它可能是这样的：
Map<ID, FlatObject> flatObjectMap = new HashMap<ID, FlatObject>();
for (FlatObject object: flatStructure) {
flatObjectMap.put(object.ID, object);
}
还要查找每个父级：
private FlatObject getParent(FlatObject object) {
getRealObject(object.ParentID);
}
private FlatObject getRealObject(ID objectID) {
flatObjectMap.get(objectID);
}
getRealObject(ID)并从对象到对象集合（或其ID）进行映射，您也可以获得父->子映射。假设字典是类似于TreeMap的东西，我可以用4行代码和O(n log n)时间完成这个任务。
dict := Dictionary new.
ary do: [:each | dict at: each id put: each].
ary do: [:each | (dict at: each parent) addChild: each].
root := dict at: nil.
编辑： 好的，现在我读到一些parentIDs是假的，所以忘记上面的内容，做这个：
dict := Dictionary new.
dict at: nil put: OrderedCollection new.
ary do: [:each | dict at: each id put: each].
ary do: [:each |
(dict at: each parent ifAbsent: [dict at: nil])
add: each].
roots := dict at: nil.
var rootNodes = new List<DTIntranetMenuItem>();
var dictIntranetMenuItems = new Dictionary<long, DTIntranetMenuItem>();
//Convert the flat database items to the DTO's,
//that has a list of children instead of a ParentID.
foreach (var efIntranetMenuItem in flatIntranetMenuItems) //List<tblIntranetMenuItem>
{
//Automapper (nuget)
DTIntranetMenuItem intranetMenuItem =
Mapper.Map<DTIntranetMenuItem>(efIntranetMenuItem);
intranetMenuItem.Children = new List<DTIntranetMenuItem>();
dictIntranetMenuItems.Add(efIntranetMenuItem.ID, intranetMenuItem);
}
foreach (var efIntranetMenuItem in flatIntranetMenuItems)
{
//Getting the equivalent object of the converted ones
DTIntranetMenuItem intranetMenuItem = dictIntranetMenuItems[efIntranetMenuItem.ID];
if (efIntranetMenuItem.ParentID == null || efIntranetMenuItem.ParentID <= 0)
{
rootNodes.Add(intranetMenuItem);
}
else
{
var parent = dictIntranetMenuItems[efIntranetMenuItem.ParentID.Value];
parent.Children.Add(intranetMenuItem);
//intranetMenuItem.Parent = parent;
}
}
return rootNodes;
你是否只能使用这些属性？如果不是，创建一个子节点数组可能会很好，这样你可以循环遍历所有这些对象一次来构建这些属性。从那里开始，选择具有子节点但没有父节点的节点，并从上到下迭代构建你的树。
这个解决方案与所选答案相同，但使用JavaScript实现：
/**
* @param {{id: any, parentId: any}[]} nodes
*/
function arrayToTree(nodes) {
const map = new Map(nodes.map((x) => [x.id, { key: x.id, children: [] }]));
for (const n of nodes) {
if (n.parentId) {
map.get(n.parentId)?.children?.push(map.get(n.id));
}
}
return nodes.filter((x) => x.parentId === null).map((x) => map.get(x.id));
}
package tree;
import java.util.*;
import java.util.function.Consumer;
import java.util.stream.Stream;
public class Tree {
private <T> void swap(T[] input, int a, int b) {
T tmp = input[a];
input[a] = input[b];
input[b] = tmp;
}
public static void main(String[] args) {
Random r = new Random(8);
MyObject[] myObjects = new MyObject[]{
new MyObject(6, 3),
new MyObject(7, 5),
new MyObject(8, 0),
new MyObject(1, 0),
new MyObject(15, 12),
new MyObject(12, 0),
new MyObject(3, 5),
new MyObject(4, 3),
new MyObject(5, 2),
new MyObject(2, 1),
new MyObject(21, 8),
new MyObject(9, 1)
};
Tree t = new Tree();
// cinco trocas arbitrarias de posição
for (int i = 0; i < 5; i++) {
int a = r.nextInt(7) + 1;
int b = r.nextInt(7) + 1;
t.swap(myObjects, a, b);
}
System.out.println("The list have " + myObjects.length + " objects");
for (MyObject o: myObjects) {
System.out.print(" " + o);
}
Iterator<Node> iterator = t.buildTreeAndGetRoots(Arrays.asList(myObjects));
int counter = 0;
System.out.println("");
while (iterator.hasNext()) {
Node obj = iterator.next();
System.out.println(++counter + "\t" + obj.associatedObject.id + "\t-> " + obj.associatedObject.parentId);
}
}
Iterator<Node> buildTreeAndGetRoots(List<MyObject> actualObjects) {
Node root = null;
Map<Integer, Node> lookup = new HashMap<>();
actualObjects.forEach(x -> lookup.put(x.id, new Node(x)));
Stream<Node> roots = actualObjects.stream()
.filter(x -> x.parentId == 0)
.map(x -> new Node(x));
Consumer<Node> nodeConsumer = item -> {
Node proposedParent;
if (lookup.containsKey(item.associatedObject.parentId)) {
proposedParent = lookup.get(item.associatedObject.parentId);
item.parent = proposedParent;
proposedParent.children.add(item);
}
};
lookup.values().forEach(nodeConsumer);
Stream<Node> s2 = lookup.values().stream().filter(e -> e.associatedObject.parentId != 0);
return Stream.concat(roots, s2).iterator();
}
}
class MyObject { // The actual object
public int parentId;
public int id;
MyObject(int id, int parent) {
this.parentId = parent;
this.id = id;
}
@Override
public String toString() {
return "{ " +
"parent: " + parentId +
", id: " + id +
" }" ;
}
}
class Node {
public List<Node> children = new ArrayList<Node>();
public Node parent;
public MyObject associatedObject;
public Node(MyObject associatedObject) {
this.associatedObject = associatedObject;
}
}