<p>为了简化此过程,我们定义一个简单的关系对象:</p>
<pre><code>class Node(dict):
def __init__(self, uid):
self._parent = None # pointer to parent Node
self['id'] = uid # keep reference to id #
self['children'] = [] # collection of pointers to child Nodes
@property
def parent(self):
return self._parent # simply return the object at the _parent pointer
@parent.setter
def parent(self, node):
self._parent = node
# add this node to parent's list of children
node['children'].append(self)
</code></pre>
<p>接下来定义如何将节点集合相互关联。我们将使用dict保存指向每个单独节点的指针:</p>
<pre><code>def build(idPairs):
lookup = {}
for uid, pUID in idPairs:
# check if was node already added, else add now:
this = lookup.get(uid)
if this is None:
this = Node(uid) # create new Node
lookup[uid] = this # add this to the lookup, using id as key
if uid != pUID:
# set this.parent pointer to where the parent is
parent = lookup[pUID]
if not parent:
# create parent, if missing
parent = Node(pUID)
lookup[pUID] = parent
this.parent = parent
return lookup
</code></pre>
<p>现在,获取输入数据并将其关联起来:</p>
<pre><code>a = [(1, 1), (2, 1), (3, 1), (4, 3), (5, 3), (6, 3), (7, 7), (8, 7), (9, 7)]
lookup = build(a) # can look at any node from here.
for uid in [1, 3, 4]:
parent = lookup[uid].parent
if parent:
parent = parent['id']
print "%s's parent is: %s" % (uid, parent)
</code></pre>
<p>最后,获得输出:很有可能您希望将数据作为唯一树的列表而不是字典植根,但是您可以选择您喜欢的内容。</p>
<pre><code>roots = [x for x in lookup.values() if x.parent is None]
# and for nice visualization:
import json
print json.dumps(roots, indent=4)
</code></pre>
<p>屈服:</p>
<pre><code>[
{
"id": 1,
"children": [
{
"id": 2,
"children": []
},
{
"id": 3,
"children": [
{
"id": 4,
"children": []
},
{
"id": 5,
"children": []
},
{
"id": 6,
"children": []
}
]
}
]
},
{
"id": 7,
"children": [
{
"id": 8,
"children": []
},
{
"id": 9,
"children": []
}
]
} ]
</code></pre>