Как заменить поддерево в питоне

Question

У меня древовидная структура данных, как показано ниже:

class Node(object): 
    def __init__(self, data): 
     self.data  = data 
     self.children = [] 
    def add_child(self, obj): 
     self.children.append(obj) 

Затем я создал метод, чтобы достигнуть его.

def replace(node, newNode): 
    if node.data == 1: 
     node = newNode 
     return 
    else: 
     for i in xrange(0, len(node.children)): 
      replace(node.children[i], newNode) 

Этот метод называется просто так:

replace(mytree,newNode) 

Поскольку это рекурсивный вызов, я думаю, что объект разрушаться и назначение не происходит.

Я попробовал его вручную:

mytree.children[0].children[0] = newNode 

то дерево правильно обновляется. Как я могу достичь этого, используя мой метод выше?

Answer 1

Назначение node = newNode не делает то, что вы хотите. Он не заменяет объект, который вы знаете как node с newNode всюду. Он просто перезаписывает имя локальной переменной node, чтобы указать на тот же объект, что и другое локальное имя newNode. Другие ссылки на первый узел (например, в списке его родителя children) не будут изменены.

Чтобы сделать то, что вы хотите, требуется больше тонкости. Лучший подход часто часто не заменяет узел вообще, а скорее заменяет его содержимое. То есть установите node.data и node.children равными newNode.data и newNode.children и оставьте node на месте. Это не работает должным образом, если есть другие ссылки на node или newNode, и вы хотите, чтобы они правильно работали после замены.

Альтернативой является замена в родительском узле, который вы ищете. Это не будет работать в верхней части вашего дерева, поэтому вам понадобится специальная логика для обработки этой ситуации.

def replace(node, newNode): 
    if node.value == 1: 
     raise ValueError("can't replace the current node this way") 

    for index, child in enumerate(node.children): 
     if child.data == 1: 
      node.children[index] = newNode 
      return True 

     if replace(child, newNode): 
      return True 

    return False 

Я также добавил дополнительную логику, чтобы остановить рекурсивную обработку дерева, когда соответствующий узел был найден. Функция вернет True, если была произведена замена, или False, если не указано значение data.