迭代预序k进树遍历

我的python代码当前打印出k-ary树中从根到叶的每个节点的名称。但是，我希望有子> 1的分支节点的名称可以打印n次;其中n =儿童人数。迭代预序k进树遍历

对于上述树 enter image description here

我的代码打印以下

不过，我希望它打印以下

start 
a 
b 
d 
f 
end 
b 
c 
e 
end 
d 
c 
e 
end

我想节点b和d打印因为他们有两个孩子，所以两次（按正确的顺序）。

我觉得这比我做的更简单。我需要添加访问过的节点列表吗？但是，我还需要知道访问次数？

一个警告是，只有具有（n.tag ==前缀+'决定'或n.tag ==前缀+'任务'）的节点才会有多个孩子。所以，我可以保留一个决策/任务节点的列表以及它们被访问的次数。如果访问次数==孩子的数量，从列表中弹出节点？

我觉得我过度复杂化了很多。

这是一个简单的例子，但是我的代码需要为k-ary工作。（我知道我的示例树只是二进制）。

我的代码如下：

from itertools import izip 
import xml.etree.ElementTree as ET 

def main(): 

    prefix = "{http://jbpm.org/4.4/jpdl}" 

    xml = ET.parse("testWF2.xml") 
    root = xml.getroot() 
    i = root.findall('*') 

    # convert list to dictionary indexed by Element.name 
    temp = [] 
    for it in i: 
     name = it.get("name") 
     if (name): 
      temp.append(name) 
     else: 
      tag = it.tag 
      temp.append(tag.replace(prefix, '')) # if no name exists use tag (ex. start and end) 
    b = dict(izip(temp, i)) # create the dictionary with key = name 

    nodes = [] 
    # add root to the list 
    nodes.append(b["start"]) 

    while(nodes): 

     n = nodes.pop() 
     transitions = n.findall(prefix+"transition") 
     children = [] 
     # get all of n's children 
     for t in transitions: 
      children.append(b[t.get("to")]) 

     for child in children: 
      nodes.append(child) # add child 

     if (not n.get("name")): 
      print ("start") 
     else: 
      print(n.get("name")) 

    # end while loop 

main()

如果有人需要看到testWF2.xml文件，它在这里 http://bpaste.net/show/160832/

来源

2013-12-21 erebel55

感谢您提供足够的xml文件和代码来使用它。顺便说一下，为什么你想要双列出父项？如果是为了消除歧义，你真的需要从根目录列出整个路径，对不对？ – KobeJohn

为了您的特殊要求粘贴，我改变它，这样每次迭代与工程父母和孩子。输出基于父级 - 这样父级会自动输出k次。当没有更多的孩子时，还需要特殊情况才能输出孩子。

from itertools import izip 
import xml.etree.ElementTree as ET 

def main(): 
    prefix = "{http://jbpm.org/4.4/jpdl}" 

    xml = ET.parse("testWF2.xml") 
    root = xml.getroot() 
    i = root.findall('*') 

    # convert list to dictionary indexed by Element.name 
    temp = [] 
    for it in i: 
     name = it.get("name") 
     if name: 
      temp.append(name) 
     else: 
      tag = it.tag 
      temp.append(tag.replace(prefix, '')) # if no name exists use tag (ex. start and end) 
    b = dict(izip(temp, i)) # create the dictionary with key = name 


    nodes = [] 
    # add root to the list 
    start_pair = (None, b["start"]) # # # # # using pairs 
    nodes.append(start_pair) 

    while(nodes): 
     parent, n = nodes.pop() # # # # # using pairs 
     transitions = n.findall(prefix+"transition") 
     children = [] 
     # get all of n's children 
     for t in transitions: 
      child = b[t.get("to")] 
      children.append(child) 
      nodes.append((n, child)) # add parent/child pair 

     # only output the parent (thus outputing k times) 
     try: 
      print parent.get("name", "start") 
     except AttributeError: 
      pass # ignore the start position 
     # also output the node if it has no children (terminal node) 
     if len(children) < 1: 
      print n.get("name", "start") 

    # end while loop 

main()

start 
a 
b 
d 
f 
end 
d 
c 
e 
end 
b 
c 
e 
end

来源

2013-12-21 22:40:21 KobeJohn

那不是你的图都表现出了树。这是一个图表。您可以使用DFS打印出您的图表。改变的开始和结束节点每次调用DFS为：

开始到结束
b键结束
d结束

我很抱歉，不能把它一张不错的桌子。我讨厌堆栈溢出，这使格式化非常困难。

来源

2015-05-03 05:27:41 user98158

迭代预序k进树遍历

回答

相关问题