如何将受感染的节点传播到其相邻节点，并最终传播到整个二叉树？

假设每个节点都可以访问自己的父节点，则顶级算法是在源节点处进行广度优先遍历，然后在父节点上重复该算法

Infect the origin node and put that node in a single element list called "the list"

while the list is not empty:
    infect all nodes in the list
    print the tree, as this represents the next iteration
    Update the list to contain all the children of the current list
    
After the above algorithm runs, move up the parent node of the origin node and repeat.

我认为这接近你想要的：

def virus(tree, originNode):
    while True:
        startInfectingDownward(tree, originNode)
        if not originNode.parent:
            break
        originNode = originNode.parent

def startInfectingDownward(tree, originNode):
    if (originNode.isInfected):
        return
    nextSetOfInfections = [originNode]
    while nextSetOfInfections:
       for node in nextSetOfInfections:
           node.isInfected = true
       printTree(tree)
       nextSetOfInfections = getNextSetOfInfections(nextSetOfInfections)


def getNextSetOfInfections(list):
    resultList = []
    for item in list:
       if (item.left and not item.left.isInfected):
           resultList.append(item.left)
       if (item.right and not item.right.isInfected):
           resultList.append(item.right)
    return resultList

这里是代码的修改版本，使用函数遍历树。此外，我还为每个节点添加了布尔参数，以指示节点是否被感染：.inorder.infected

from binarytree import Node, build


def build_tree(data):
    nodes = []
    for i, v in enumerate(data):
        if v == 0:
            nodes.append(None)
        else:
            n = Node(v)
            n.infected = False  # <-- node is initailly *NOT* infected
            nodes.append(n)

    for i in range(len(data)):
        left = 2 * i + 1
        right = 2 * i + 2

        if left < len(nodes) and nodes[left]:
            nodes[i].left = nodes[left]

        if right < len(nodes) and nodes[right]:
            nodes[i].right = nodes[right]

    return nodes[0]


def is_whole_tree_infected(root):
    return all(n.infected for n in root.inorder)


def search_node(root, value):
    for n in root.inorder:
        if n.value == value:
            return n


def find_parent(root, node):
    for n in root.inorder:
        if n.left is node:
            return n
        if n.right is node:
            return n


def infect(node):
    node.value = f"*{node.value}*"
    node.infected = True


def infect_neighbours(root, node):
    out = set()
    parent = find_parent(root, node)
    if parent and not parent.infected:
        out.add(parent)
    if node.left and not node.left.infected:
        out.add(node.left)
    if node.right and not node.right.infected:
        out.add(node.right)

    return out


def virus(root):
    while not is_whole_tree_infected(root):
        to_infect = set()

        for node in root.inorder:
            if node.infected:
                to_infect |= infect_neighbours(root, node)

        for n in to_infect:
            infect(n)

        print(root)


sample = ["A", "B", "C", "D", "E", 0, "F"]
origin_value = "C"

tree = build_tree(sample)
origin_node = search_node(tree, origin_value)
infect(origin_node)

print(tree)
virus(tree)

指纹：

    __A_
   /    \
  B     *C*
 / \       \
D   E       F


    __*A*_
   /      \
  B       *C*_
 / \          \
D   E         *F*


     ___*A*_
    /       \
  *B*       *C*_
 /   \          \
D     E         *F*


       _____*A*_
      /         \
   _*B*_        *C*_
  /     \           \
*D*     *E*         *F*

作为节点的邻居，您还应该考虑该节点的父节点。该包公开了一个函数，因此这很容易。binarytreeget_parent

其他一些评论：

• 不要使用 0 表示缺少节点。请改用：公开的函数将考虑到这一点，这会使您自己的函数过时。Nonebuildbinarytreebuild_tree

• 尽管您的代码将原始节点标记为受感染（通过在其值中添加星号），但您没有将此节点添加到集合中，从而使情况不一致。我建议避免此类错误，并将该函数替换为执行感染节点所需的所有功能的函数。它将设置 并添加一个属性来替换用于此目的的 set。infected_nodesinfectedinfectvalueis_infected

• virus有权访问变量，该变量是全局变量。这不是很好的做法，如果要使用多个树，就会有问题。作为参数传递给 。treetreevirus

• 退出条件可以更好地省略：让条件发挥作用。if infected_nodes == set(current_round)while

• 树中的节点是可迭代的，即当你迭代这样的节点时，你将按级别顺序获得该节点及其所有后代。您可以使用此功能大大简化您的功能。binarytreesearch_node

这是您的代码更新：

from binarytree import build, get_parent

def infect(node):  # Do all that is needed to mark a node as infected
    node.is_infected = True  # This seems more elegant than maintaining a set
    node.value = f"*{node.value}*"

def search_node(root, value):
    # The nodes are iterable, so make use of that feature
    return next(node for node in root if node.value == value)

def virus(tree, node):  # Extra argument, so we can find the parent of a node
    infect(origin_node)  # Perform the first infection inside virus()
    current_round = set([node])
    while current_round:
        print(tree)
        next_round = set()
        for current_node in current_round:
            # The node's parent is also a neighbor: 
            #    use the get_parent function from the package
            for neighbor in current_node.left, current_node.right,
                                               get_parent(tree, current_node):
                # Use of an "is_infected" attribute works fine
                if neighbor and not hasattr(neighbor, "is_infected"):
                    infect(neighbor)
                    next_round.add(neighbor)
        current_round = next_round

# Use None to indicate the absence of a node (not 0)
sample = ["A", "B", "C", "D", "E", None, "F"]
origin_value = "C"
tree = build(sample)  # Use build() from binarytree package
origin_node = search_node(tree, origin_value)
virus(tree, origin_node)  # Pass tree as argument