迭代預序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進樹遍歷

回答

相關問題