Преобразование функции рекурсивного дерева ходьбы в итеративный

Как можно преобразовать следующую рекурсивную функцию walk() в итеративную функцию?Преобразование функции рекурсивного дерева ходьбы в итеративный

Прогулка по узлам в том же порядке итерационно легко с использованием стека, но я не могу понять, как написать итеративную функцию, которая будет печатать как открывающие, так и закрывающие теги каждого узла, как рекурсивная версия.

Код:

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)

Выход:

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

код, который обходит дерево итеративно:

Функция посещает узлы в правильном порядке, но очевидно, не печатает закрытие .

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)

источник

2016-08-10 chase37

Покажите свою итерационную функцию, которая лишь частично решает эту проблему. –

Добавлен код. – chase37

Проблема в том, что для этого вам также необходимо записать в стек, где заканчивается узел. Возможным решением было бы:

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="")

Я добавил отступы поэтому выход лучше:

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

источник

2016-08-10 20:54:12 mata

Это вид post-order tree treversal как вы должны посетить родительский узел после посещения детей.

Я изменил несколько строк существующего кода:

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)

источник

2016-08-10 20:58:59 RandyTek

Преобразование функции рекурсивного дерева ходьбы в итеративный

ответ

Смежные вопросы