首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >在给定根的情况下构造树

在给定根的情况下构造树
EN

Stack Overflow用户
提问于 2018-08-30 09:45:28
回答 4查看 427关注 0票数 3

例如。根为1的[13,11], [13,8], [6, 8], [3, 6]

寻找一种Pythonic式的方法将树构建到字典中,这样我们就有了{13: [11, 8], 11: [], 3: [], 6: [3], 8: [6]}

因为我知道根,所以我的方法是用13循环遍历条目,连接这些条目,然后将这些条目视为根,依此类推。

请注意,没有排序。为了区分,我知道根(某个数字),并可以从那里确定。

有没有更好的方法?

EN

回答 4

Stack Overflow用户

发布于 2018-08-30 10:38:26

通过使用set来跟踪哪些元素已经添加到字典中,我们可以在O(n)时间内解决这个问题。一般的想法是遍历节点,检查一个节点当前是否在图中,如果是,我们在添加到字典时就知道它是父节点。

代码语言:javascript
复制
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)

在行动中:

代码语言:javascript
复制
arr = [[1,2], [1,8], [5, 8], [3, 5]]

x = MyTree(arr)
print(x.data)

代码语言:javascript
复制
defaultdict(<class 'list'>, {1: [2, 8], 8: [5], 5: [3], 2: [], 3: []})
票数 2
EN

Stack Overflow用户

发布于 2018-08-30 10:42:08

递归方法:

代码语言:javascript
复制
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))

这将输出以下内容:

代码语言:javascript
复制
{1: [2, 8], 2: [], 8: [5], 5: [3], 3: []}
票数 0
EN

Stack Overflow用户

发布于 2018-08-30 22:16:43

您可以使用广度优先搜索:

代码语言:javascript
复制
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))

输出:

代码语言:javascript
复制
defaultdict(<class 'list'>, {1: [2, 8], 8: [5], 5: [3], 2: [], 3: []})
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/52088149

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档