Python 3.5 - 'Infect opened tree branches'

Question

我知道这个标题听起来有点奇怪，当然这只是我实际需要的类比。

所以，假设我有一棵这样的树：

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

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

遍历树会感染遍历时所有'opened' branches/leaves，但不会感染新打开的。让我们假设分支 E 被感染——遍历树产生被感染的 F 和 C 分支，因为它们已经 'opened' 在这个迭代，但不是 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

如何使 'higher level' 个分支（如 C）被感染，而不影响 traverse_tree 的下一次迭代？

（我希望 'opened branches' 足够清楚，但只是为了确保它是 - 当发现受感染的分支时，这些分支已经从 for child 循环中产生）

Answer 1

好的，所以我找到了解决方案，但我想我还是会等待更好的解决方案。

我刚刚编辑了原来的 Node 并添加了 p_infected 属性。这将帮助我标记以后需要感染的所有分支。一旦我发现一些受感染的分支 - 它会感染他的所有 parents 直到根。然后，我遍历树，感染回那些分支的 children，并删除 'parent infection'.

当前代码如下所示：

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

但是，正如我之前所写，我仍然愿意接受更好的解决方案。我有一种预感，上面的内容可以只用原来的 'traversal' 函数来完成，如果有人能找到方法 - 我会很高兴..

谢谢。

Python 3.5 - 'Infect opened tree branches'

Python 3.5 - 'Infect opened tree branches'

python

tree

generic-programming