Python 3.5 - 「感染した木の枝に感染する」

Question

タイトルがちょっと変わっているのを知っていますが、もちろんこれは私が実際に必要としているものと同じです。いくつかの病気に感染した葉（または支店）の一つで

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

：

だから、私はこのような木を持っていると仮定することができます。

ツリーをトラバースすると、トラバーサル時にすべての「開かれた」ブランチ/リーフに感染しますが、は新しく開かれたものではありません。その枝を想定Eが感染していることができます - 彼らはすでにIとGこの繰り返しで「開かれた」ではなくので、木の収率は、FとC枝を感染横断します。

私がこれまで持っている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？

（私は「開かれた枝」が十分に明確ですが、ちょうどそれがあることを確認することを願っています - これらは、感染した枝が発見したとき、すでにfor childループから得枝です）

Answer 1

OK、そうI解決策を見つけましたが、私はまだもっと良いものを待つと思います。

私はちょうど元の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 

しかし、私は前に書いたように、私はまだ良い解決策に開いています。私は、上記のことが元の「トラバーサル」機能だけでできていることを知っています。誰かがどのように見つけたら、私は幸せになるでしょう。

ありがとう。