如何从邻接列表构建嵌套树结构? [英] How to build a nested tree structure from a list of adjacencies?

问题描述

考虑到我有:

• 名为 A
的相邻键(子 - 父)列表
• 一个名为 Tree 的树类存储它自己的节点键(整数)和子节点(类)

• a list of adjacent keys (child - parent) named A
• a tree class named Tree storing its own node key (integer) and children (classes)

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)))))

我正在考虑以递归方式创建树，但我不知道如何正确遍历和填充它.这是我失败的尝试:

I was thinking about creating the tree in a recursive way but I can not figure out how to traverse and populate it properly. Here is my failed attempt:

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)
        

推荐答案

你在这段代码中提到了两个问题:

You mention two issues in this piece of code:

    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 循环移动到第二个参数中来解决这些问题，以列表推导的形式并溅出该列表使它们成为参数.然后确保您的递归函数返回创建的树:

You can solve them by essentially moving the for loop into the second argument, in the form of list comprehension and splashing that list so they become arguments. And then make sure your recursive function returns the created tree:

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

更多想法

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

More ideas

Unrelated to your question, but here are some more ideas you could use.

• 建议让您的代码成为一个函数，您可以将 A 作为参数传递给该函数，这样字典的范围也只是该函数的局部范围，而不会乱扔全局范围.

• It would be advisable to make your code a function to which you can pass A as argument, so that also the dictionary's scope is just local to that function and does not litter the global scope.

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

As this feature is strongly related to the Tree class, it would be nice to define it as a static or class method within the class.

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

When you have the (child, parent) tuples for the tree, then these implicitly define which node is the root, so you could omit passing the literal 66 to your function. That function should be able to find out which is the root by itself. While creating the dictionary it can also collect which nodes have a parent. The root is then the node that is not in that collection.

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

So taking all that together you would have this:

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)

这篇关于如何从邻接列表构建嵌套树结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！