Python 3.5“感染打开的树枝”

Question

我知道这个标题听起来有点奇怪，但当然这只是一个类比，我实际上需要什么。你知道吗

假设我有一棵这样的树：

A
┃
┣━━ B
┃   ┣━━ D
┃   ┣━━ E
┃   ┃   ┗━━ H
┃   ┗━━ F
┃       ┗━━ I
┗━━ C
    ┗━━ G

其中一片叶子（或树枝）感染了某种疾病。你知道吗

遍历树将感染遍历时所有“打开”的树枝/树叶，，但不会感染新打开的树枝/树叶。让我们假设分支E被感染-遍历树产生受感染的F和C分支，因为它们已经在这个迭代中“打开”，而不是I和G。你知道吗

到目前为止，我的python代码是（infection_test.py）：

#!/usr/bin/env python
from itertools import chain

class Node():
    def __init__(self, name, infected=False):
        self.name = name
        self.children = []

        self.infected = infected

    def __str__(self):
        return 'Node ' + self.name + (' *** INFECTED ***' if self.infected else '')

A = Node('A');B = Node('B');C = Node('C')
D = Node('D');E = Node('E', True);F = Node('F');
G = Node('G');H = Node('H');I = Node('I');

A.children = [B, C]
B.children = [D, E, F]
E.children = [H]
F.children = [I]
C.children = [G]

def traverse_tree(node, level=0):
    print ('    '*level, node)
    level += 1
    infected_found = False
    for child in node.children:
        if child.infected:
            infected_found = True
        traverse_tree(child, level)
        child.infected = infected_found

print('First traversal:')
traverse_tree(A)
print('\nAfter Infection:')
traverse_tree(A)

输出：

First traversal:
 Node A
     Node B
         Node D
         Node E *** INFECTED ***
             Node H
         Node F
             Node I
     Node C
         Node G

After Infection:
 Node A
     Node B
         Node D
         Node E *** INFECTED ***
             Node H
         Node F *** INFECTED ***
             Node I
     Node C
         Node G

如何使“更高级别”的分支（如C）受到感染，而不影响traverse_tree的下一次迭代？你知道吗

（我希望‘opened branchs’足够清晰，但要确保它是这样的——当被感染的分支被发现时，这些分支已经从for child循环中产生了）

Answer 1

好吧，我找到了一个解决办法，但我想我还是会等一个更好的。你知道吗

我刚刚编辑了原始的Node并添加了p_infected属性。这将有助于我标记所有的分支，我需要感染以后。当我发现一些被感染的分支-它感染了他所有的父母直到根。然后，我穿过这棵树，感染那些树枝的子树，去除“父感染”。你知道吗

当前代码如下所示：

from itertools import chain

class Node():
    def __init__(self, name, infected=False, p_infected=False):
        ...
        self.parent   = None
        self.p_infected = p_infected

    def add_children(self, childs = []):
        self.children.extend(childs)
        for node in childs:
            node.parent = self

    def __str__(self):
        return 'Node ' + self.name + \
        (' ***INFECTED***' if self.infected else '') + \
        (' ***P_INFECTED***' if self.p_infected else '')

A = Node('A');B = Node('B');C = Node('C')
D = Node('D',True);E = Node('E');F = Node('F');
G = Node('G');H = Node('H');I = Node('I');

A.add_children([B,H])
B.add_children([C, D, F])
D.add_children([E])
F.add_children([G])
H.add_children([I])

def infect_parent(node):
    if node.parent:
        node.parent.p_infected = True
        infect_parent(node.parent)

def traverse_tree(node, level=0):
    print ('    '*level + str(node))
    if node.infected:
        node.p_infected = True
        infect_parent(node)
    level += 1
    for child in node.children:
        traverse_tree(child, level)


def infect_children(node):
    infect_flag = False
    for child in node.children:
        if infect_flag:
            child.infected = True
        infect_flag = child.p_infected
        infect_children(child)

def remove_parent_infection(node):
    node.p_infected = False
    for child in node.children:
        remove_parent_infection(child)

print('First travesal:')
traverse_tree(A)
infect_children(A)
remove_parent_infection(A)
print('\nAfter infection:')
traverse_tree(A)

以及所需的输出：

First travesal:
Node A
    Node B
        Node C
        Node D ***INFECTED***
            Node E
        Node F
            Node G
    Node H
        Node I

After infection:
Node A
    Node B
        Node C
        Node D ***INFECTED***
            Node E
        Node F ***INFECTED***
            Node G
    Node H ***INFECTED***
        Node I

但是，正如我之前写的，我仍然对更好的解决方案持开放态度。我有一个预感，上面可以做只是原来的'遍历'功能，如果有人能找到如何-我会很高兴。。你知道吗

谢谢。你知道吗