Đệ quy xây dựng cây JSON phân cấp?

Question

Tôi có một cơ sở dữ liệu về các kết nối cha-con. Dữ liệu trông giống như sau nhưng có thể được trình bày theo bất kỳ cách nào bạn muốn (từ điển, danh sách danh sách, JSON, v.v.).

links=(("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Bob","Leroy"),("Bob","Earl")) 

Kết quả mà tôi cần là cây JSON phân cấp, sẽ được hiển thị bằng d3. Có những cây con rời rạc trong dữ liệu mà tôi sẽ gắn vào nút gốc. Vì vậy, tôi cần phải đệ quy đi mặc dù các liên kết, và xây dựng cấu trúc cây. Điều xa nhất tôi có thể nhận được là lặp lại tất cả mọi người và thêm con cái của họ, nhưng tôi không thể tìm ra các liên kết đặt hàng cao hơn (ví dụ: cách nối thêm một người có con với con của người khác). Điều này tương tự như một câu hỏi khác here, nhưng tôi không có cách nào để biết các nút gốc trước, vì vậy tôi không thể triển khai giải pháp được chấp nhận.

Tôi sẽ tìm cấu trúc cây sau đây từ dữ liệu mẫu của tôi.

{ 
"name":"Root", 
"children":[ 
    { 
    "name":"Tom", 
    "children":[ 
     { 
     "name":"Dick", 
     "children":[ 
      {"name":"Harry"} 
     ] 
     }, 
     { 
      "name":"Larry"} 
    ] 
    }, 
    { 
    "name":"Bob", 
    "children":[ 
     { 
     "name":"Leroy" 
     }, 
     { 
     "name":"Earl" 
     } 
    ] 
    } 
] 
} 

Cấu trúc này hiển thị như thế này trong bố cục d3 của tôi.

Answer 1

Để xác định các ghi chú rễ bạn có thể giải nén links và tìm kiếm cha mẹ không phải là trẻ em:

parents, children = zip(*links) 
root_nodes = {x for x in parents if x not in children} 

Sau đó, bạn có thể áp dụng phương pháp đệ quy:

import json 

links = [("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Bob","Leroy"),("Bob","Earl")] 
parents, children = zip(*links) 
root_nodes = {x for x in parents if x not in children} 
for node in root_nodes: 
    links.append(('Root', node)) 

def get_nodes(node): 
    d = {} 
    d['name'] = node 
    children = get_children(node) 
    if children: 
     d['children'] = [get_nodes(child) for child in children] 
    return d 

def get_children(node): 
    return [x[1] for x in links if x[0] == node] 

tree = get_nodes('Root') 
print json.dumps(tree, indent=4) 

tôi đã sử dụng một bộ để có được các nút gốc, nhưng nếu thứ tự quan trọng bạn có thể sử dụng danh sách và remove the duplicates.

Answer 2

thử mã follwing:

import json 

links = (("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Tom","Hurbert"),("Tom","Neil"),("Bob","Leroy"),("Bob","Earl"),("Tom","Reginald")) 

name_to_node = {} 
root = {'name': 'Root', 'children': []} 
for parent, child in links: 
    parent_node = name_to_node.get(parent) 
    if not parent_node: 
     name_to_node[parent] = parent_node = {'name': parent} 
     root['children'].append(parent_node) 
    name_to_node[child] = child_node = {'name': child} 
    parent_node.setdefault('children', []).append(child_node) 

print json.dumps(root, indent=4) 

Answer 3

Trong trường hợp bạn muốn để định dạng dữ liệu như một hệ thống phân cấp trong HTML/JS bản thân, hãy xem tại địa chỉ:

Generate (multilevel) flare.json data format from flat json

Trong trường hợp bạn có rất nhiều dữ liệu chuyển đổi Web sẽ nhanh hơn vì nó sử dụng chức năng giảm trong khi Python thiếu lập trình hàm.

BTW: Tôi cũng đang làm việc trên cùng một chủ đề, tức là tạo cấu trúc cây có thể thu gọn trong d3.js. Nếu bạn muốn làm việc cùng, email của tôi là: erprateek.vit@gmail.com.