CODEWITHSUNDEEP
pythonalgorithmpython-2.7treetree-traversal
erebel55
erebel55

Reputation: 600

Iterative preorder k-ary tree traversal

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/

Upvotes: 2

Views: 1024

Answers (2)

user98158
user98158

Reputation: 23

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:

  1. Start to end
  2. b to end
  3. d to end

Upvotes: 0

KobeJohn
KobeJohn

Reputation: 7545

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

Upvotes: 1

Related Questions