利用python如何将无限分类结构的数据，转换成json格式数据。

Question

id text pid

1 My Documents 0
2 photos 1
3 Friend 2
4 Wife 2
5 Company 2
6 Program Files 1
7 Intel 6
8 Java 6

数据库中是以上结构，如何写段代码生成如下结构的json数据？

[{

"id":1,
"text":"My Documents",
"children":[{
    "id":2,
    "text":"Photos",
    "children":[{
        "id":3,
        "text":"Friend"
    },{
        "id":4,
        "text":"Wife"
    },{
        "id":5,
        "text":"Company"
    }]
},{
    "id":6,
    "text":"Program Files",
    "children":[{
        "id":7,
        "text":"Intel"
    },{
        "id":8,
        "text":"Java",
    }]
}]

}]

Answer 1

递归的方式虽然比较好理解，但是用哈希表做的话时间复杂度低很多

import json

source=[
    {"name":"my document","id":1 , "parentid": 0 },
    {"name":"photos","id":2 , "parentid": 1 },
    {"name":"Friend","id":3 , "parentid": 2 },
    {"name":"Wife","id":4 , "parentid": 2 },
    {"name":"Company","id":5 , "parentid": 2 },
    {"name":"Program Files","id":6 , "parentid": 1 },
    {"name":"intel","id":7 , "parentid": 6 },
    {"name":"java","id":8 , "parentid": 6 },
]

tree_dict = {}
tree_data = []

for item in source:
    tree_dict[item["id"]] = item

for i in tree_dict:
    if tree_dict[i]["parentid"]:
        parentid = tree_dict[i]["parentid"]
        parent = tree_dict[parentid]
        parent.setdefault("children",[]).append(tree_dict[i])

    else:
        tree_data.append(tree_dict[i])

res = json.dumps(tree_data)
print(res)

结果

[
    {
        "name": "my document",
        "id": 1,
        "parentid": 0,
        "children": [
            {
                "name": "photos",
                "id": 2,
                "parentid": 1,
                "children": [
                    {
                        "name": "Friend",
                        "id": 3,
                        "parentid": 2
                    },
                    {
                        "name": "Wife",
                        "id": 4,
                        "parentid": 2
                    },
                    {
                        "name": "Company",
                        "id": 5,
                        "parentid": 2
                    }
                ]
            },
            {
                "name": "Program Files",
                "id": 6,
                "parentid": 1,
                "children": [
                    {
                        "name": "intel",
                        "id": 7,
                        "parentid": 6
                    },
                    {
                        "name": "java",
                        "id": 8,
                        "parentid": 6
                    }
                ]
            }
        ]
    }
]

时间复杂度为
O(2n)

Answer 2

import json
source=[
    {"name":"my document","id":1 , "parentid": 0 },
    {"name":"photos","id":2 , "parentid": 1 },
    {"name":"Friend","id":3 , "parentid": 2 },
    {"name":"Wife","id":4 , "parentid": 2 },
    {"name":"Company","id":5 , "parentid": 2 },
    {"name":"Program Files","id":6 , "parentid": 1 },
    {"name":"intel","id":7 , "parentid": 6 },
    {"name":"java","id":8 , "parentid": 6 },
]

def getChildren(id=0):
    sz=[]
    for obj in source:
        if obj["parentid"] ==id:
            sz.append({"id":obj["id"],"text":obj["name"],"children":getChildren(obj["id"])})
    return sz

print json.dumps(getChildren())

[
  {
    "text": "my document",
    "id": 1,
    "children": [
      {
        "text": "photos",
        "id": 2,
        "children": [
          {
            "text": "Friend",
            "id": 3,
            "children": [ ]
          },
          {
            "text": "Wife",
            "id": 4,
            "children ": [ ]
          },
          {
            "text": "Company",
            "id": 5,
            "children": [ ]
          }
        ]
      },
      {
        "text": "Program Files",
        "id": 6,
        "children": [
          {
            "text": "intel",
            "id": 7,
            "children": [ ]
          },
          {
            "text": "java",
            "id ": 8,
            "children": [ ]
          }
        ]
      }
    ]
  }
]

代码比较粗糙，性能不好，主要借鉴下思想吧