Konvertieren rekursive Tree Walking-Funktion zu iterativen

Wie kann die folgende rekursive Funktion walk() in eine iterative Funktion umgewandelt werden? Die Knoten in derselben Reihenfolge iterativ zu durchlaufen, ist einfach, wenn man einen Stapel benutzt, aber ich kann nicht herausfinden, wie man eine iterative Funktion schreibt, die die öffnenden und schließenden Tags jedes Knotens wie die rekursive Version ausgibt.Konvertieren rekursive Tree Walking-Funktion zu iterativen

Code:

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

def walk(node): 
    print('<', node.name, '>', sep='') 
    for n in node.children: 
     walk(n) 
    print('</', node.name, '>', sep='') 

root = \ 
Node('html', [ 
    Node('head'), 
    Node('body', [ 
     Node('div'), 
     Node('p', [ 
      Node('a'), 
     ]) 
    ]), 
]) 

walk(root)

Ausgang:

<html> 
<head> 
</head> 
<body> 
<div> 
</div> 
<p> 
<a> 
</a> 
</p> 
</body> 
</html>

Code, der den Baum iterativ durchläuft:

Die Funktion, die die Knoten in der richtigen Reihenfolge besucht, aber offensichtlich druckt das clos nicht Tags

def walk(node): 
    stack = [] 
    stack.append(node) 
    while len(stack) > 0: 
     node = stack.pop() 
     for child in reversed(node.children): 
      stack.append(child) 
     print(node.name)

Quelle

2016-08-10 chase37

Zeigen Sie Ihre iterative Funktion, die das Problem löst nur teilweise. –

Der Code wurde hinzugefügt. – chase37

Das Problem ist, dass für diese Arbeit müssen Sie auch auf dem Stapel aufzeichnen, wo der Knoten endet. Eine mögliche Lösung wäre:

def walk(root): 
    stack = [] 
    stack.append(root) 
    indent = 0 
    while stack: 
     node = stack.pop() 
     if isinstance(node, Node): 
      print(' ' * indent, "<", node.name, ">", sep="") 
      indent += 1 
      stack.append(node.name) 
      stack.extend(reversed(node.children)) 
     else: 
      indent -= 1 
      print(' ' * indent, "</", node, ">", sep="")

ich so die Ausgabe Einrückungen hinzugefügt haben ist schöner:

<html> 
    <head> 
    </head> 
    <body> 
     <div> 
     </div> 
     <p> 
      <a> 
      </a> 
     </p> 
    </body> 
</html>

Quelle

2016-08-10 20:54:12 mata

Es Art von post-order tree treversal ist, wie Sie den übergeordneten Knoten nach dem Besuch Kinder zu besuchen.

modifizierte ich ein paar Zeilen Ihrer bestehenden Code:

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

# def walk(node): 
#  print('<', node.name, '>', sep='') 
#  for n in node.children: 
#   walk(n) 
#  print('</', node.name, '>', sep='') 

def walk(node): 
    stack = [] 
    stack.append((node, 'start')) 
    while len(stack) > 0: 
     node, status = stack.pop() 
     if status == 'start': 
      stack.append((node, 'end')) 
      for child in reversed(node.children): 
       stack.append((child, 'start')) 
      print('<', node.name, '>', sep='') 
     else: # status == 'end' 
      print('</', node.name, '>', sep='') 

root = \ 
Node('html', [ 
    Node('head'), 
    Node('body', [ 
     Node('div'), 
     Node('p', [ 
      Node('a'), 
     ]) 
    ]), 
]) 

walk(root)

Quelle

2016-08-10 20:58:59 RandyTek

Konvertieren rekursive Tree Walking-Funktion zu iterativen

Antwort

Verwandte Themen