Iterative preorder k-ary tree traversal

Question

My python code currently prints out the name of each node in a k-ary tree, from the root to leafs. However, I would like the name of branch nodes with children > 1 to print out n times; where n = number of children.

For the above tree enter image description here

My code prints the following

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

However, I want it to print the following

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

I want nodes b and d to print out twice (in the correct order) since they have two children.

I feel like this is more simple than I am making it out to be. Do I need to add a list of nodes visited? But then I would need to know the number of times visited as well?

One caveat is that only nodes with (n.tag == prefix + 'decision' or n.tag == prefix + 'task') will ever have more than one child. So, I could keep a list of decision/task nodes and the number of times they have been visited. If the number of times visited == number of children, pop the node from the list?

I feel like I am over complicating this a lot.

This is a simple example, however my code needs to work for k-ary. (I know my example tree is only binary).

My code is below:

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()

If anyone needs to see the testWF2.xml file it is pasted here http://bpaste.net/show/160832/

Thanks for providing the xml file and code enough to use it. By the way, why would you want to double-list the parent? If it's for disambiguation, you would really need to list the whole path from root, wouldn't you? — KobeJohn
– KobeJohn, Commented Dec 21, 2013 at 22:44

KobeJohn · Accepted Answer · 2013-12-22 01:45:39Z

For your special requirement, I changed it so that each iteration works with the parent and the child. The output is based on the parent - in that way the parent automatically is output k-times. It also needs a special case to output the child when there are no further children.

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

Nimantha · Accepted Answer · 2021-11-04 12:59:01Z

That's not a tree which you have shown in diagram. It is a graph. You can use DFS to print out your diagram. change the start and end nodes for each call to DFS as:

Start to end
b to end
d to end

Collectives™ on Stack Overflow

Iterative preorder k-ary tree traversal

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related