时间戳

首页 > 解决方案 > 树人 js 的 Python 递归函数

python - 树人 js 的 Python 递归函数

问题描述

我正在尝试为 treant js 库生成一棵树，但是，查看他们期望的 JSON 格式让我在按照他们的需要正确生成树时遇到了一些困难。

目前，这是我所做的：

这是库想要的输出：

"""
output = {
    metric_1 : {
        name : 'metric 1', desc: 'desc', contact: 'form * x - y'
    },
    children: [{
        metric_2 : {
            name : 'metric 2', desc: 'desc', contact: 'form * x - y'
        },
    },
    // Metric 2 has children, add the children attribute on the same level as metric_2
    children : [{
        ...
    }],
    {
        metric_3 : {
            name : 'metric 3', desc: 'desc', contact: 'form * x - y'
        }
    },
    ]
}
"""

这是我的尝试：

def get_records():
    # ID, Tree ID, Metric Name, Metric Description, Metric Formula, Parent, ReferenceID
    records = (('1', '1', 'metric 1', 'desc', 'form * x  - y', '', 'metric_1'),
    ('2', '1', 'metric 2', 'desc', 'form * x  - y', 'metric_1', 'metric_2'),
    ('3', '1', 'metric 3', 'desc', 'form * x  - y', 'metric_1', 'metric_3'),
    ('4', '1', 'metric 4', 'desc', 'form * x  - y', 'metric_2', 'metric_4'),
    ('5', '1', 'metric 5', 'desc', 'form * x  - y', 'metric_2', 'metric_5'))
    return records


def generate_output(record, output={}):
    def generate(record):
        #print(output)
        # rowno, tree_id, metric_name, metric_desc, metric_form, parent, refid
        try:
            output['children'].append({record[6] : {'name': record[2], 'title': record[3], 'contact': record[4]}})
        except KeyError:
            output[record[6]] = {'name': record[2], 'title': record[3], 'contact': record[4]}
        if children:=find_children(record[6]):
            try:
                if output['children']:
                    pass
            except KeyError:
                output['children'] = []
            for child in children:
                generate(child)
    generate(record)
    return output

def find_children(argrefid):
    records = get_records()
    output = []
    for record in records:
        if record[5] == argrefid:
            output.append(record)
    return output

if __name__ == '__main__':
    for record in get_records():
        print(generate_output(record))
        break 
    # Need to only pass the first element to recursively create the tree

第一个周期按预期工作，但是我发现很难在children他们请求的度量的同一级别上递归地创建一个数组，这就是我的程序输出的内容：

{'metric_1': {'name': 'metric 1', 'title': 'desc', 'contact': 'form * x  - y'}, 'children': [{'metric_2': {'name': 'metric 2', 'title': 'desc', 'contact': 'form * x  - y'}}, {'metric_4': {'name': 'metric 4', 'title': 'desc', 'contact': 'form * x  - y'}}, {'metric_5': {'name': 'metric 5', 'title': 'desc', 'contact': 'form * x  - y'}}, {'metric_3': {'name': 'metric 3', 'title': 'desc', 'contact': 'form * x  - y'}}]}

但是，正如我所说，我希望将度量 4 和度量 5 作为其父级 metric2 的子级。

任何帮助是极大的赞赏。

标签： pythonrecursiontreerecursive-datastructures

解决方案

我不会递归地解决这个问题，而是迭代地解决这个问题：

  1. 在一个步骤中从每条记录构建项目
  2. 在第二步中将他们与各自的父母联系起来

样本

import json

def get_records():
           # ID, TreeID, MetricName, MetricDescription, MetricFormula, Parent, ReferenceID
    return (('1', '1', 'metric 1', 'desc', 'form * x  - y', '', 'metric_1'),
            ('2', '1', 'metric 2', 'desc', 'form * x  - y', 'metric_1', 'metric_2'),
            ('3', '1', 'metric 3', 'desc', 'form * x  - y', 'metric_1', 'metric_3'),
            ('4', '1', 'metric 4', 'desc', 'form * x  - y', 'metric_2', 'metric_4'),
            ('5', '1', 'metric 5', 'desc', 'form * x  - y', 'metric_2', 'metric_5'))

records = get_records()

# 1. build all entries and index them by their referene ID
entry_by_ref = {}
for record in records:
    entry_by_ref[record[6]] = {
        'name': record[2],
        'title': record[3],
        'contact': record[4],
    }

# 2. find root node and link all others into a tree
root = None
for record in records:
    entry = entry_by_ref.get(record[6])
    parent = entry_by_ref.get(record[5])
    if record[5] == '':
        root = entry
    elif parent is not None:
        if 'children' not in parent:
            parent['children'] = []
        parent['children'].append(entry)

print(json.dumps(root, indent=2))

上述输出：

{
  "name": "metric 1",
  "title": "desc",
  "contact": "form * x  - y",
  "children": [
    {
      "name": "metric 2",
      "title": "desc",
      "contact": "form * x  - y",
      "children": [
        {
          "name": "metric 4",
          "title": "desc",
          "contact": "form * x  - y"
        },
        {
          "name": "metric 5",
          "title": "desc",
          "contact": "form * x  - y"
        }
      ]
    },
    {
      "name": "metric 3",
      "title": "desc",
      "contact": "form * x  - y"
    }
  ]
}

推荐阅读