如何通过“冒泡”每个子树的值来展平树？

Question

我有以下树数据结构：class TreeNode:    def __init__(self, path, value=None):        self.path = path        self.value = value        self.children = []path目录或文件名在哪里。如果 的值为path文件（树中的叶子），则值为整数，否则为None. 这是此树结构的示例：└── root (None)    ├── dir0 (None)    |   ├── dir00 (None)    |   |   └── file000.txt (10)    |   └── file00.txt (10)    ├── dir1 (None)    |   └── file10.txt (5)    ├── dir2 (None)    |   ├── file20.txt (10)    |   └── file21.txt (15)    └── dir3 (None)        ├── dir30 (None)        |   └── file300.txt (15)        └── file30.txt (10)我正在尝试返回已解决路径及其关联的最小可能展平列表value。如果子树中的所有节点都具有相同的value，那么我们说这样的子树与value它的节点相同。本质上，value如果父节点的所有子节点都具有相同的value.例如，上面的树应该返回的是：/root/dir0: 10/root/dir1: 5/root/dir2/file20.txt: 10/root/dir2/file21.txt: 15/root/dir3/dir30: 15/root/dir3/file30.txt: 10我尝试了几种不同的方法来实现这一点：用堆栈遍历树，用递归遍历树，以及使用集合；一切都失败了。我最近尝试的伪代码如下所示：def build_list(self, treenode):    if treenode.value:        return [(treenode.path, treenode.value)]    if treenode.value == None:        s = set()        for child in treenode.children:            potential_values = self.build_list(child)            for val in potential_values:                s |= {val[1]}        if len(s) == 1:            return [(treenode.path, treenode.value)]        else:            return [(child.path, child.value) for child in treenode.children]我将如何做到这一点？伪代码完全没问题，我正在寻找一种方法，不一定是完整的实现。

Answer 1

方法一

递归应该起作用：

def recurse_update_value(treenode):

    if not treenode.children:

        return

    for child in treenode.children:

        recurse_update_value(child)

    if all(x.value==treenode.children[0].value for x in treenode.children):

        treenode.value = treenode.children[0].value

        treenode.children = []

方法二

此外，如果您可以编辑 TreeNode 类，则可以将 getter 方法设置为自动更新子类。

class TreeNode:

    def __init__(self, path, value=None):

        self.path = path

        self._value = value

        self.children = []

    @property

    def value(self)

        if not self.children:

            return self._value

        first_child_value = self.children[0].value

        if all(x.value==first_child_value for x in self.children)

            self._value = first_child_value

            self.children = []

        return self._value

然后，您只需调用topnode.value即可更新树。

Answer 2

这是一种方法。我正在使用不同的节点类来使设置更容易一些：

class TreeNode:

    def __init__(self, node_id, value=None):

        self.node_id = node_id

        self.value = value

        self.children = []

    def addChildren(self, *node_list):

        self.children += node_list

    def __repr__(self):

        return f'<TreeNode(node_id={self.node_id}, value={self.value})'

__repr__()只是为了在打印时获得人类可读的实例表示。

我试图设置树来反映您的示例，但如果它不完全正确，请随时告诉我。（它可以做得更简洁，但为了清楚起见，我已经为每个对象写了一行。）

root = TreeNode('root')

dir0 = TreeNode('dir0')

dir00 = TreeNode('dir00')

file00 = TreeNode('file00', 10)

file000 = TreeNode('file000', 10)

dir1 = TreeNode('dir1')

file10 = TreeNode('file10', 5)

dir2 = TreeNode('dir2')

file20 = TreeNode('file20', 10)

file21 = TreeNode('file21', 15)

dir3 = TreeNode('dir3')

dir30 = TreeNode('dir30')

file30 = TreeNode('file30', 10)

file300 = TreeNode('file300', 15)

root.addChildren(dir0, dir1, dir2, dir3)

dir0.addChildren(dir00, file00)

dir00.addChildren(file000)

dir1.addChildren(file10)

dir2.addChildren(file20, file21)

dir3.addChildren(dir30, file30)

dir30.addChildren(file300)

现在对于递归函数：

def buildList(node):

    # Return node id and value if no children

    if not node.children:

        return [(node.node_id, node.value)]

    # Call buildList on each child and get distinct values

    childitems = [item for child in node.children for item in buildList(child)]

    childvalues = set(childitem[1] for childitem in childitems)

    # If value is unique, return this node as if it has the unique value

    if len(childvalues) == 1:

        return [(node.node_id, childvalues.pop())]

    # Otherwise, return all results

    return childitems

这会产生以下输出：

>>> buildList(root)

[('dir0', 10),

 ('dir1', 5),

 ('file20', 10),

 ('file21', 15),

 ('dir30', 15),

 ('file30', 10)]

[编辑] 请注意，这将返回一个列表并且不会改变节点。

关于您的特定实现，您可能想考虑如果有一个空目录会发生什么。这是允许的吗？如果是这样，它是一片叶子，而不是一个文件。在这种情况下它会有价值吗？