[Tutor] treeTraversal, nested return?

[spir]

On Fri, 4 Jun 2010 10:15:26 -0700 (PDT)
jjcrump at uw.edu wrote:

> All,
> 
> any observations might be helpful. For the display of database contents I 
> have the following problem:
> 
> Database querys will return data to me in tuples of the following sort:
> each tuple has a unique id, a parent id, and a type.
> 
> a parent id of 0 indicates that the element has no parent.
> not all data elements have children
> image elements have no children and must have a parent
> 
> So the contents of the db is a tree of sorts:
> 
> (1, 0, work)
> (555, 1, image)
> (556, 1, work)
> (557, 556, image)
> (558, 556, work)
> (559, 558, image)
> (560, 558, work)
> (561, 556, image)
> (562, 556, image)
> (563, 1, work)
> (564, 563, work)
> (565, 1, work)
> 
> I have a function that will traverse this tree, summoning lists of tuples 
> at each leaf. Well and good; it took a lot of trial and error, but it was 
> a fine education in tree traversal.
> 
> def makeHeirarchy(id):
>      id = parentPath(id)[-1]
>      rootimages = getImages(id[0])
>      rootworks = getWorks(id[0])
>      heirarchy = treeTraversal(rootworks, [id, rootimages])
>      return heirarchy
> 
> ## which calls this recursive function:
> 
> def treeTraversal(listIn,result):
>      for x in listIn:
>          if not getWorks(x[0]):
>              result.append(x)
>              result.append(getImages(x[0]))
>          else:
>              result.append(x)
>              result.append(getImages(x[0]))
>              treeTraversal(getWorks(x[0]), result)
>      return result
> 
> My problem is that this returns the tuples to me in a flat list.
> I've been trying to work out how I can get it to return some sort of 
> nested structure: nested lists, dictionaries, or html thus:

For an indented output, you're simply forgetting to inform the recursive function aobut current indent level. Example (note: a nested sequence is not a tree: it has no root):

SPACE , WIDTH, NODE, NL = " " , 4 , "<node>" , '\n'

def indentOutput(s, level=0):
	# fake root
	if level == 0:
		text = NODE
	else:
		text = ""
	# children
	level += 1
	offset = level * SPACE * WIDTH
	for element in s:
		if isinstance(element, (tuple,list)):
			text += "%s%s%s%s" %(NL,offset,NODE , indentOutput(element, level))
		else:
			text += "%s%s%s" %(NL,offset,element)
	return text

s = (1,(2,3),4,(5,(6,7),8),9)
print indentOutput(s)

<node>
    1
    <node>
        2
        3
    4
    <node>
        5
        <node>
            6
            7
        8
    9


Denis
________________________________

vit esse estrany ☣

spir.wikidot.com