如何从不利的表示中恢复树形结构?

huangapple go评论94阅读模式
英文:

How to recover a tree structure from an unfavorable representation of one?

问题

以下是您要翻译的内容:

"Let's say we have an unfavorable representation of a tree. This tree is not nested, but flattened and its nodes are 'connected' only by ids:

{
   'nodes':[
      {
         'id':0,
         'value':'and',
         'children':[
            1,
            4
         ]
      }
      {
         'id':1,
         'value':'or',
         'children':[
            2,
            3
         ]
      },
      {
         'id':4,
         'value':'or',
         'children':[
            5,
            6
         ]
      }
   ],
   'leafs':[
      {
         'id':2,
         'value':'some statement'
      },
      {
         'id':3,
         'value':'some statement'
      },
      {
         'id':5,
         'value':'some statement'
      },
      {
         'id':6,
         'value':'some statement'
      }
   ]
}"


<details>
<summary>英文:</summary>

Let&#39;s say we have an unfavorable representation of a tree. This tree is not nested, but flattened and its nodes are &quot;connected&quot; only by ids:

{
"nodes":[
{
"id":0,
"value":"and",
"children":[
1,
4
]
}
{
"id":1,
"value":"or",
"children":[
2,
3
]
},
{
"id":4,
"value":"or",
"children":[
5,
6
]
}
],
"leafs":[
{
"id":2,
"value":"some statement"
},
{
"id":3,
"value":"some statement"
},
{
"id":5,
"value":"some statement"
},
{
"id":6,
"value":"some statement"
}
]
}


You can see that the tree is not only flattened, there is also a rather unnecessary representation of the leafs as a dedicated list.
The ids of the leafs are therefore appearing twice: Once as a child in its parent node and once as an identifier of the leaf.

What I want is a nested representation of this tree as dedicated python objects. I have to substitute the &quot;id&quot; with the whole object and get rid of the overly complicated list representation.

This is what I want:

{
"tree": {
"id": 0,
"value": "and",
"children": [
{
"id": 1,
"value": "or",
"children": [
{
"id": 2,
"value": "some statement"
},
{
"id": 3,
"value": "some statement"
}
]
},
{
"id": 4,
"value": "or",
"children": [
{
"id": 6,
"value": "some statement"
},
{
"id": 6,
"value": "some statement"
}
]
}
]
}
}


How would I start to parse the two lists, so that I can build python objects (node and leaf classes), that reference each other and are representing this tree structure just by reference.

class Node:
def init(self, id, operator):
self.id = id
self.value= operator
self.children = None

class Leaf:
def init(self, id, operator):
self.id = id
self.value = None


These are my tree classes, but I don&#39;t know how to traverse the two list in a way that brings me to my desired tree.

</details>


# 答案1
**得分**: 1

你可以将你的树形数据转换成字典,以 `id` 作为键,以 `node_data` 作为值。

**代码:**
```python
class Node:
    def __init__(self, node_id: int, operator: str, children: Optional[list] = None):
        self.id = node_id
        self.value = operator
        self.children = children

    def __repr__(self):
        return f'Node(id={self.id}, value={self.value})'


def build_tree(start: int, nodes: dict):
    node_data = nodes[start]
    node = Node(node_data['id'], node_data['value'])
    if node_data.get('children'):
        node.children = [build_tree(child, nodes) for child in node_data.get('children')]
    return node

nodes = {node['id']: node for node in data['leafs']}
nodes.update({node['id']: node for node in data['nodes']})

root = build_tree(0, nodes)

在上面的代码中,我创建了一个名为 Node 的类,用于维护所有的值,对于叶子节点,children 参数将会是 None

更新:

如果你将 Node 类作为 pydantic 模型使用:

from pydantic import BaseModel
from typing import List, Optional

class Node(BaseModel):
    id: int
    value: str
    children: Optional[List['Node']]

    def to_dict(self) -> dict:
        return {'tree': self.dict()}

在上面的 pydantic 模型中,我添加了一个 to_dict() 方法,它将返回树的字典表示。

示例输出:

{
    'tree': {
        'id': 0,
        'value': 'and',
        'children': [
            {
                'id': 1,
                'value': 'or',
                'children': [
                    {'id': 2, 'value': 'some statement', 'children': None},
                    {'id': 3, 'value': 'some statement', 'children': None},
                ],
            },
            {
                'id': 4,
                'value': 'or',
                'children': [
                    {'id': 5, 'value': 'some statement', 'children': None},
                    {'id': 6, 'value': 'some statement', 'children': None},
                ],
            },
        ],
    }
}
英文:

You can convert your tree data to the dictionary with id as the key and node_data as the value.

Code:


class Node:
    def __init__(self, node_id: int, operator: str, children: Optional[list] = None):
        self.id = node_id
        self.value = operator
        self.children = children

    def __repr__(self):
        return f&#39;Node(id={self.id}, value={self.value})&#39;


def build_tree(start: int, nodes: dict):
    node_data = nodes[start]
    node = Node(node_data[&#39;id&#39;], node_data[&#39;value&#39;])
    if node_data.get(&#39;children&#39;):
        node.children = [build_tree(child, nodes) for child in node_data.get(&#39;children&#39;)]
    return node


nodes = {node[&#39;id&#39;]: node for node in data[&#39;leafs&#39;]}
nodes.update({node[&#39;id&#39;]: node for node in data[&#39;nodes&#39;]})

root = build_tree(0, nodes)

In the code I have created a class Node that maintains all the values, for leaf nodes children parameter will be None.

Update:

If you are using Node class as pydantic model

class Node(BaseModel):
    id: int
    value: str
    children: Optional[List[&#39;Node&#39;]]

    def to_dict(self) -&gt; dict:
        return {&#39;tree&#39;: self.dict()}

In the above pydantic model, I have added to_dict() method that will return that dictionary representation of the tree

Sample Output:

{
    &#39;tree&#39;: {
        &#39;id&#39;: 0,
        &#39;value&#39;: &#39;and&#39;,
        &#39;children&#39;: [
            {
                &#39;id&#39;: 1,
                &#39;value&#39;: &#39;or&#39;,
                &#39;children&#39;: [
                    {&#39;id&#39;: 2, &#39;value&#39;: &#39;some statement&#39;, &#39;children&#39;: None},
                    {&#39;id&#39;: 3, &#39;value&#39;: &#39;some statement&#39;, &#39;children&#39;: None},
                ],
            },
            {
                &#39;id&#39;: 4,
                &#39;value&#39;: &#39;or&#39;,
                &#39;children&#39;: [
                    {&#39;id&#39;: 5, &#39;value&#39;: &#39;some statement&#39;, &#39;children&#39;: None},
                    {&#39;id&#39;: 6, &#39;value&#39;: &#39;some statement&#39;, &#39;children&#39;: None},
                ],
            },
        ],
    }
}

huangapple
  • 本文由 发表于 2023年6月29日 00:15:23
  • 转载请务必保留本文链接:https://go.coder-hub.com/76575014.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定