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

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

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:

  1. {
  2.    'nodes':[
  3.       {
  4.          'id':0,
  5.          'value':'and',
  6.          'children':[
  7.             1,
  8.             4
  9.          ]
  10.       }
  11.       {
  12.          'id':1,
  13.          'value':'or',
  14.          'children':[
  15.             2,
  16.             3
  17.          ]
  18.       },
  19.       {
  20.          'id':4,
  21.          'value':'or',
  22.          'children':[
  23.             5,
  24.             6
  25.          ]
  26.       }
  27.    ],
  28.    'leafs':[
  29.       {
  30.          'id':2,
  31.          'value':'some statement'
  32.       },
  33.       {
  34.          'id':3,
  35.          'value':'some statement'
  36.       },
  37.       {
  38.          'id':5,
  39.          'value':'some statement'
  40.       },
  41.       {
  42.          'id':6,
  43.          'value':'some statement'
  44.       }
  45.    ]
  46. }"
  49. <details>
  50. <summary>英文:</summary>
  52. 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"
}
]
}

  2. You can see that the tree is not only flattened, there is also a rather unnecessary representation of the leafs as a dedicated list.
  3. 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.
  5. 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.
  7. 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"
}
]
}
]
}
}

  2. 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

  2. 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.
  4. </details>
  7. # 答案1
  8. **得分**: 1
  10. 你可以将你的树形数据转换成字典，以 `id` 作为键，以 `node_data` 作为值。
  12. **代码:**
  13. ```python
  14. class Node:
  15.     def __init__(self, node_id: int, operator: str, children: Optional[list] = None):
  16.         self.id = node_id
  17.         self.value = operator
  18.         self.children = children
  20.     def __repr__(self):
  21.         return f'Node(id={self.id}, value={self.value})'
  24. def build_tree(start: int, nodes: dict):
  25.     node_data = nodes[start]
  26.     node = Node(node_data['id'], node_data['value'])
  27.     if node_data.get('children'):
  28.         node.children = [build_tree(child, nodes) for child in node_data.get('children')]
  29.     return node
  31. nodes = {node['id']: node for node in data['leafs']}
  32. nodes.update({node['id']: node for node in data['nodes']})
  34. root = build_tree(0, nodes)

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

更新:

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

  1. from pydantic import BaseModel
  2. from typing import List, Optional
  4. class Node(BaseModel):
  5.     id: int
  6.     value: str
  7.     children: Optional[List['Node']]
  9.     def to_dict(self) -> dict:
  10.         return {'tree': self.dict()}

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

示例输出:

  1. {
  2.     'tree': {
  3.         'id': 0,
  4.         'value': 'and',
  5.         'children': [
  6.             {
  7.                 'id': 1,
  8.                 'value': 'or',
  9.                 'children': [
  10.                     {'id': 2, 'value': 'some statement', 'children': None},
  11.                     {'id': 3, 'value': 'some statement', 'children': None},
  12.                 ],
  13.             },
  14.             {
  15.                 'id': 4,
  16.                 'value': 'or',
  17.                 'children': [
  18.                     {'id': 5, 'value': 'some statement', 'children': None},
  19.                     {'id': 6, 'value': 'some statement', 'children': None},
  20.                 ],
  21.             },
  22.         ],
  23.     }
  24. }
英文:

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

Code:

  2. class Node:
  3.     def __init__(self, node_id: int, operator: str, children: Optional[list] = None):
  4.         self.id = node_id
  5.         self.value = operator
  6.         self.children = children
  8.     def __repr__(self):
  9.         return f&#39;Node(id={self.id}, value={self.value})&#39;
  12. def build_tree(start: int, nodes: dict):
  13.     node_data = nodes[start]
  14.     node = Node(node_data[&#39;id&#39;], node_data[&#39;value&#39;])
  15.     if node_data.get(&#39;children&#39;):
  16.         node.children = [build_tree(child, nodes) for child in node_data.get(&#39;children&#39;)]
  17.     return node
  20. nodes = {node[&#39;id&#39;]: node for node in data[&#39;leafs&#39;]}
  21. nodes.update({node[&#39;id&#39;]: node for node in data[&#39;nodes&#39;]})
  23. 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

  1. class Node(BaseModel):
  2.     id: int
  3.     value: str
  4.     children: Optional[List[&#39;Node&#39;]]
  6.     def to_dict(self) -&gt; dict:
  7.         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:

  1. {
  2.     &#39;tree&#39;: {
  3.         &#39;id&#39;: 0,
  4.         &#39;value&#39;: &#39;and&#39;,
  5.         &#39;children&#39;: [
  6.             {
  7.                 &#39;id&#39;: 1,
  8.                 &#39;value&#39;: &#39;or&#39;,
  9.                 &#39;children&#39;: [
  10.                     {&#39;id&#39;: 2, &#39;value&#39;: &#39;some statement&#39;, &#39;children&#39;: None},
  11.                     {&#39;id&#39;: 3, &#39;value&#39;: &#39;some statement&#39;, &#39;children&#39;: None},
  12.                 ],
  13.             },
  14.             {
  15.                 &#39;id&#39;: 4,
  16.                 &#39;value&#39;: &#39;or&#39;,
  17.                 &#39;children&#39;: [
  18.                     {&#39;id&#39;: 5, &#39;value&#39;: &#39;some statement&#39;, &#39;children&#39;: None},
  19.                     {&#39;id&#39;: 6, &#39;value&#39;: &#39;some statement&#39;, &#39;children&#39;: None},
  20.                 ],
  21.             },
  22.         ],
  23.     }
  24. }

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

发表评论

匿名网友

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

确定