在给定根的情况下构造树
在给定根的情况下构造树
提问于 2018-08-30 09:45:28
例如。根为1的[13,11], [13,8], [6, 8], [3, 6]
寻找一种Pythonic式的方法将树构建到字典中，这样我们就有了{13: [11, 8], 11: [], 3: [], 6: [3], 8: [6]}
因为我知道根，所以我的方法是用13循环遍历条目，连接这些条目，然后将这些条目视为根，依此类推。
请注意，没有排序。为了区分，我知道根(某个数字)，并可以从那里确定。
有没有更好的方法？
回答 4
Stack Overflow用户
发布于 2018-08-30 10:38:26
通过使用set来跟踪哪些元素已经添加到字典中，我们可以在O(n)时间内解决这个问题。一般的想法是遍历节点，检查一个节点当前是否在图中，如果是，我们在添加到字典时就知道它是父节点。
from collections import defaultdict
class MyTree:
def __init__(self, data):
self.data = defaultdict(list)
self.seen = set()
for node in data:
self.add_node(node)
for el in self.seen:
if el not in self.data:
self.data[el] = []
def add_node(self, el):
x, y = el
if y in self.seen:
self.data[y].append(x)
else:
self.data[x].append(y)
self.seen.update(el)在行动中：
arr = [[1,2], [1,8], [5, 8], [3, 5]]
x = MyTree(arr)
print(x.data)
defaultdict(<class 'list'>, {1: [2, 8], 8: [5], 5: [3], 2: [], 3: []})Stack Overflow用户
发布于 2018-08-30 10:42:08
递归方法：
d = [[1,2], [1,8], [5, 8], [3, 5]]
def t(d, r):
o = {r: []}
n = []
for e in d:
if r in e:
if e[1] == r:
e = e[::-1]
o[e[0]].append(e[1])
else:
n.append(e)
for i in o[r]:
o.update(t(n, i))
return o
print(t(d, 1))这将输出以下内容：
{1: [2, 8], 2: [], 8: [5], 5: [3], 3: []}Stack Overflow用户
发布于 2018-08-30 22:16:43
您可以使用广度优先搜索：
import collections
data = [[1,2], [1,8], [5, 8], [3, 5]]
def bfs(d, _start = lambda x:x[0][0]):
_queue, _result, _seen = collections.deque([_start(d)]), collections.defaultdict(list), []
while _queue:
v = _queue.popleft()
r = [i[0] if i[-1] == v else i[-1] for i in d if v in i]
_r = [i for i in r if i not in _seen]
_result[v].extend(_r)
_queue.extend(_r)
_seen.extend(_r+[v])
return _result
print(bfs(data))输出：
defaultdict(<class 'list'>, {1: [2, 8], 8: [5], 5: [3], 2: [], 3: []})页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52088149
复制相关文章
相似问题
腾讯云开发者
