1

Я получаю из БД объекты являющиеся записями каталогов из бд которые отсортированы в виде дерева:

id:2; parent_id:1; level:1; name:parent 1
id:5; parent_id:2; level:2; name:child 1 - 1
id:6; parent_id:2; level:2; name:child 1 - 2
id:9; parent_id:2; level:2; name:child 1- 3
id:7; parent_id:5; level:3; name:child 1 - 1 - 1
id:11; parent_id:6; level:3; name:children 2- 1
id:10; parent_id:7; level:4; name:child 4 levl parent 1
id:3; parent_id:1; level:1; name:parent 2
id:13; parent_id:3; level:2; name:parent 2- 1 - chil
id:4; parent_id:1; level:1; name:parent 3
id:8; parent_id:1; level:1; name:parent 4

Список уже отсортирован в виде дерева, т.е. идет родительский раздел (level 1), затем, если есть дочерние, потом следующий раздел 1ого уровня. Мне нужно эти данные привести к такому виду словаря:

tree = {}
tree['parent 1'] = {}
tree['parent 1']['child 1 - 1'] = {}
tree['parent 1']['child 1 - 1']['child 1 - 1 - 1'] = {}
tree['parent 1']['child 1 - 1']['child 1 - 1 - 1']['child 4 levl parent 1'] = {}
tree['parent 1']['child 1 - 2'] = {}
tree['parent 1']['child 1 - 2']['children 2- 1'] = {}
tree['parent 1']['child 1- 3'] = {}
tree['parent 1']['child1']['child3'] = {} 

tree['parent 2'] = {}
tree['parent 2']['parent 2- 1 - chil'] = {}

tree['parent 3'] = {}
tree['parent 4'] = {}

Уже 2ой день не могу придумать как сделать. Как бы все данные есть, есть понимание уровня вложенности через levle и родителя через parent_id. И если создать 1 уровень несложно, то как сделать 2ой и особенно 3 и далее? Если кто сталкивался или делал такое, пожалуйста, подскажите

1

4 ответа 4

1
def buildsubtrees(rows):
    trees = {}

    for row in rows:
        trees.setdefault(row['parent_id'], {})[row['name']] = trees.setdefault(row['id'], {})

    return trees

Принимает набор записей, и возвращает словарь, в котором ключами будут id родителей, а значениями - соответствующие им поддеревья. Вас интересует поддерево с ключом 1, т.е. дерево целиком. Порядок поступления записей не важен, сложность линейная.

import json # для форматированного вывода

rows = [
    {'id':  2, 'parent_id': 1, 'level': 1, 'name': 'parent 1'},
    {'id':  5, 'parent_id': 2, 'level': 2, 'name': 'child 1 - 1'},
    {'id':  6, 'parent_id': 2, 'level': 2, 'name': 'child 1 - 2'},
    {'id':  9, 'parent_id': 2, 'level': 2, 'name': 'child 1- 3'},
    {'id':  7, 'parent_id': 5, 'level': 3, 'name': 'child 1 - 1 - 1'},
    {'id': 11, 'parent_id': 6, 'level': 3, 'name': 'children 2- 1'},
    {'id': 10, 'parent_id': 7, 'level': 4, 'name': 'child 4 levl parent 1'},
    {'id':  3, 'parent_id': 1, 'level': 1, 'name': 'parent 2'},
    {'id': 13, 'parent_id': 3, 'level': 2, 'name': 'parent 2- 1 - chil'},
    {'id':  4, 'parent_id': 1, 'level': 1, 'name': 'parent 3'},
    {'id':  8, 'parent_id': 1, 'level': 1, 'name': 'parent 4'},
]

print(json.dumps(buildsubtrees(rows)[1], indent=4))

Результат

{
    "parent 1": {
        "child 1 - 1": {
            "child 1 - 1 - 1": {
                "child 4 levl parent 1": {}
            }
        },
        "child 1 - 2": {
            "children 2- 1": {}
        },
        "child 1- 3": {}
    },
    "parent 2": {
        "parent 2- 1 - chil": {}
    },
    "parent 3": {},
    "parent 4": {}
}
1

Хотел расписать как это делать, но решил питон вспомнить...

Сори, что коряво, но собственно по сути, как строить дерево. Работает по ID, типа print(M[1][2][6]).

Свой вариант сам додумаешь надеюсь...

Удачи.

'''

X = [
{"id":2, "parent_id":1, "level":1,  "name":"parent 1"},
{"id":5, "parent_id":2, "level":2,  "name":"child 1 - 1"},
{"id":6, "parent_id":2, "level":2,  "name":"child 1 - 2"},
{"id":9, "parent_id":2, "level":2,  "name":"child 1- 3"},
{"id":7, "parent_id":5, "level":3,  "name":"child 1 - 1 - 1"},
{"id":11, "parent_id":6, "level":3, "name":"children 2- 1"},
{"id":10, "parent_id":7, "level":4, "name":"child 4 levl parent 1"},
{"id":3, "parent_id":1, "level":1,  "name":"parent 2"},
{"id":13, "parent_id":3, "level":2, "name":"parent 2- 1 - chil"},
{"id":4, "parent_id":1, "level":1,  "name":"parent 3"},
{"id":8, "parent_id":1, "level":1,  "name":"parent 4"}
]

def fillMap(level, lists, parent, M):
  if(len(lists) > level):
    for i in lists[level]:
      if(i["parent_id"] == parent):
        M[i["id"]] = {}
        M[i["id"]] = fillMap(level + 1, lists, i["id"], M[i["id"]])
  return M


def output(tree, space):
  for i in tree:
    print(space + str(i))
    output(tree[i], space + " ")

listLevels = [[],[],[],[]]
for i in X:
  listLevels[i["level"]-1].append(i)

M = {1:{}}

fillMap(0, listLevels, 1, M[1])

output(M, "")

'''

1
  1. Нужно распарсить входные данные — записи разделить по \n, элементы по ;, ключи-значения по :
  2. Собрать дерево. Так как в питоне объекты передаются по ссылкам, то можно обходить ноды, и для каждой отдельно добавлять потомков. А в итоговое дерево поместить ноды, у которых parent_id == 1 (корень).
values = """id:2; parent_id:1; level:1; name:parent 1
id:5; parent_id:2; level:2; name:child 1 - 1
id:6; parent_id:2; level:2; name:child 1 - 2
id:9; parent_id:2; level:2; name:child 1- 3
id:7; parent_id:5; level:3; name:child 1 - 1 - 1
id:11; parent_id:6; level:3; name:children 2- 1
id:10; parent_id:7; level:4; name:child 4 levl parent 1
id:3; parent_id:1; level:1; name:parent 2
id:13; parent_id:3; level:2; name:parent 2- 1 - chil
id:4; parent_id:1; level:1; name:parent 3
id:8; parent_id:1; level:1; name:parent 4
"""

def parse(data):
    parsed = {}
    for item in values.strip().split("\n"):
        node = {}
        for el in item.split(";"):
            el = el.strip()
            key, value = el.split(":")
            node[key] = value
        parsed[node["id"]] = node
    return parsed

def build_tree(parsed):
    tree = {}
    nodes = {}
    for item in parsed.values():
        node = nodes.setdefault(item["name"], {})
        if item["parent_id"] == "1":
            # this is root node, without parent
            tree[item["name"]] = node
            continue
        parent = nodes.setdefault(parsed[item["parent_id"]]["name"], {})
        parent[item["name"]] = node
    return tree

tree = build_tree(parse(values))

Результат:

{'parent 1': {'child 1 - 1': {'child 1 - 1 - 1': {'child 4 levl parent 1': {}}},
  'child 1 - 2': {'children 2- 1': {}},
  'child 1- 3': {}},
 'parent 2': {'parent 2- 1 - chil': {}},
 'parent 3': {},
 'parent 4': {}}
1

Спасибо, понял идею, реализовал так:

  # Возвращает дерево
    def tree(self):
        db_tree = [
{"id":2, "parent_id":1, "level":1,  "name":"parent 1"},
{"id":5, "parent_id":2, "level":2,  "name":"child 1 - 1"},
{"id":6, "parent_id":2, "level":2,  "name":"child 1 - 2"},
{"id":9, "parent_id":2, "level":2,  "name":"child 1- 3"},
{"id":7, "parent_id":5, "level":3,  "name":"child 1 - 1 - 1"},
{"id":11, "parent_id":6, "level":3, "name":"children 2- 1"},
{"id":10, "parent_id":7, "level":4, "name":"child 4 levl parent 1"},
{"id":3, "parent_id":1, "level":1,  "name":"parent 2"},
{"id":13, "parent_id":3, "level":2, "name":"parent 2- 1 - chil"},
{"id":4, "parent_id":1, "level":1,  "name":"parent 3"},
{"id":8, "parent_id":1, "level":1,  "name":"parent 4"}
]
        db_tree = self.buildTree(db_tree)
        return db_tree
    # Строит узел дерева
    def buildTree(self, db_tree):
        tree = {}
        index = {row["id"]: row for row in db_tree}
        for row in db_tree:
            self.processRowTree(row, index, tree)
        return tree
    # Строит строку узла дерева
    def processRowTree(self, row, index, tree):
        if row is None:
            return tree
        parent = index.get(row["parent_id"], None)
        subtree = self.processRowTree(parent, index, tree)
        if row["name"] not in subtree:
            subtree[row["name"]] = {}

        return subtree[row["name"]]

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.