Получить все узлы на данном уровне в двоичном дереве с Python - PullRequest
Новая
       9

Получить все узлы на данном уровне в двоичном дереве с Python

0 голосов
/ 04 сентября 2018

Я пытаюсь получить список узлов (objetcs) в двоичном дереве Python, я ищу рекурсивную функцию, реализованную в объекте узла, поэтому я вызову функцию на корневом узле, и она будет работать вниз дочерние узлы, пока не достигнут определенного уровня, а затем вернут эти узлы в список

Мой текущий подход, я не уверен, правильно ли это или лучший способ реализовать это: 

def get_level_nodes(self, nodes, level=1):
    if self.level > level:
        return nodes
    if self.level == level:
        nodes.append(self)
        return nodes
    for child in self.child_id:
        nodes += child.get_level_nodes(node, level)
    return nodes

# Getting the list
nodes_list = root_node.get_level_nodes([], 3)

1 Ответ

0 голосов
/ 04 сентября 2018

Нет необходимости передавать список узлов. Каждый узел может просто вернуть соответствующие узлы уровня своего собственного поддерева и оставить объединение соседей для родителя: 

def get_level_nodes(self, level=1):
    if self.level > level:
        return []
    if self.level == level:
        return [self]
    # child_id seems an odd name
    return [n for c in self.children for n in c.get_level_nodes(level)]

Более компактной реализацией, которая не создает промежуточные списки для каждого поддерева, была бы функция генератора: 

def get_level_nodes(self, level=1):
    if self.level > level:
        return
    if self.level == level:
        yield self
    else:
        for c in self.children:
            for n in c.get_level_nodes(level):
                yield n
            # or in Python3
            # yield from c.get_level_nodes(level)


nodes_list = list(root_node.get_level_nodes(3))
...