Как сгладить дерево, «взбивая» значения каждого поддерева?

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.

Например, что должно быть возвращено с указанным выше деревомis:

/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

Метод 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 = []

---

Метод 2

Дополнительно, еслиВы можете редактировать класс TreeNode, вы можете настроить метод get для автоматического обновления дочерних элементов.

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

[Edit] Обратите внимание, что это возвращает список и не изменяет узлы.

Что касается вашей конкретной реализации, вы можете подумать о том, что произойдет, если есть пустоекаталог.Это разрешено?Если так, то это лист, а не файл.Будет ли это иметь значение в этом случае?