如何仅查找和替换树中第一次出现的节点？

Question

您能否建议如何仅查找和替换树中的第一个左节点。我已经实现了替换所有节点的方法：

from dataclasses import dataclass, field
import typing 
from typing import List

@dataclass()
class Node:
  value: str
  children: List[Node] = field(default_factory=lambda: [])

# replaces all nodes
def substitute(source, original, replacement):
  if source == original:
    source.value = replacement.value
    source.children = replacement.children
    return source
  else:
    source.children = [substitute(child, original, replacement) for child in source.children]
    return source 

t1 = Node('r', [Node('r2', [Node('2')]), Node('2')])
substitute(t1, Node('2'), Node('5')) # will substitue all Node('2') -> Node('5')

如何实现仅替换 Node('2') 的第一个左边出现（后序）的方法？

Node('r', [Node('r2', [Node('2')]), Node('2')]) -> Node('r', [Node('r2', [Node('5')]), Node('2')])

Answer 1

由于您的 substitute 函数 改变了 给定的树，因此没有必要也拥有它 return它。

您可以改为 return 一个布尔值，指示是否已完成替换。

这样你就可以编写一个替代的 substitute_first 函数并检测递归调用是否 returned True，这将是一个不再做任何替换的信号，但是只是 return True 给调用者，所以快速退出递归树。

代码如下：

def substitute_first(source, original, replacement):
  if any(substitute_first(child, original, replacement) for child in source.children):
      return True  # A replacement was made in recursion
  if source == original:
    source.value = replacement.value
    source.children = replacement.children
    return True
  return False

如何仅查找和替换树中第一次出现的节点？

How to find and replace only first occurrence of a node in a tree?

python

tree