将递归树行走功能转换为迭代

如何将以下递归函数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>

代码：

功能访问节点以正确的顺序，但显然不打印关闭ing标签。

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

将递归树行走功能转换为迭代

回答

相关问题