时间戳

首页 > 解决方案 > 如何从邻接列表构建嵌套树结构？

python - 如何从邻接列表构建嵌套树结构？

问题描述

考虑到我有：

A = [(61, 66), (50, 61), (68, 61), (33, 61), (57, 66), (72, 66), (37, 68), (71, 33), (6, 50), (11, 37), (5, 37)]

class Tree:
    def __init__(self, node, *children):
        self.node = node
        if children: self.children = children
        else: self.children = []
    
    def __str__(self): 
        return "%s" % (self.node)
    def __repr__(self):
        return "%s" % (self.node)

    def __getitem__(self, k):
        if isinstance(k, int) or isinstance(k, slice): 
            return self.children[k]
        if isinstance(k, str):
            for child in self.children:
                if child.node == k: return child

    def __iter__(self): return self.children.__iter__()

    def __len__(self): return len(self.children)

如何构建一个 Tree 对象，使其根据邻接关系封装所有内部树？（如下所示）

t = Tree(66, 
        Tree(72), 
        Tree(57), 
        Tree(61, 
            Tree(33,
                Tree(71)), 
            Tree(50, 
                Tree(6)), 
            Tree(68, 
                Tree(37, 
                    Tree(11), Tree(5)))))

我正在考虑以递归方式创建树，但我无法弄清楚如何正确遍历和填充它。这是我失败的尝试：

from collections import defaultdict

# Create a dictionary: key = parent, values = children
d = defaultdict(list)
for child, parent in A:
    d[parent].append(child)

# Failed attempt
def build_tree(k):    
    if k in d:
        tree = Tree(k, d[k]) #1st issue: should input a Tree() as 2nd parameter
        for child in d[k]:
            build_tree(child) #2nd issue: should populate tree, not iterate recursively over children keys

#I know that the root node is 66.
full_tree = build_tree(66)

标签： pythonrecursiontreetraversal

解决方案

您在这段代码中提到了两个问题：

    tree = Tree(k, d[k]) #1st issue: should input a Tree() as 2nd parameter
    for child in d[k]:
        build_tree(child) #2nd issue: should populate tree, not iterate recursively over children keys

您可以通过本质上将for循环移动到第二个参数中来解决它们，以列表理解的形式并飞溅该列表，使它们成为参数。然后确保您的递归函数返回创建的树：

    return Tree(k, 
        *[build_tree(child) for child in d[k]]
    )

更多创意

与您的问题无关，但这里有一些您可以使用的更多想法。

  • 建议使您的代码成为可以A作为参数传递的函数，这样字典的范围也只是该函数的本地范围，并且不会乱扔全局范围。

  • 由于此功能与类密切相关Tree，因此最好将其定义为类中的静态或类方法。

  • 当您拥有树的 (child, parent) 元组时，这些元组会隐式定义哪个节点是根，因此您可以省略将文字 66 传递给您的函数。该函数应该能够自己找出哪个是根。在创建字典时，它还可以收集哪些节点有父节点。根是不在该集合中的节点。

所以把所有这些放在一起你会得到这个：

from collections import defaultdict

class Tree:
    def __init__(self, node, *children):
        self.node = node
        self.children = children if children else []
    
    def __str__(self): 
        return "%s" % (self.node)
    
    def __repr__(self):
        return "%s" % (self.node)

    def __getitem__(self, k):
        if isinstance(k, int) or isinstance(k, slice): 
            return self.children[k]
        if isinstance(k, str):
            for child in self.children:
                if child.node == k:
                    return child

    def __iter__(self):
        return self.children.__iter__()

    def __len__(self):
        return len(self.children)

    @classmethod
    def from_pairs(Cls, pairs):
        # Turn pairs into nested dictionary
        d = defaultdict(list)
        children = set()
        for child, parent in pairs:
            d[parent].append(child)
            # collect nodes that have a parent
            children.add(child)
        
        # Find root: it does not have a parent
        root = next(parent for parent in d if parent not in children)

        # Build nested Tree instances recursively from the dictionary
        def subtree(k):
            return Cls(k, *[subtree(child) for child in d[k]])

        return subtree(root)

# Sample run
A = [(61, 66), (50, 61), (68, 61), (33, 61), (57, 66), (72, 66), (37, 68), (71, 33), (6, 50), (11, 37), (5, 37)]

tree = Tree.from_pairs(A)

推荐阅读