Software and life, mostly life.

01 June 2008

Simple tree using a Python dictionary

What I already have: table with rows containing (NodeId, ParentId, Title) values.

What I need: a simple tree structure mapping Nodes to their parents.

Solution:

# simple tree builder.

# (node, parent, title)
els = (
(1, 0, 'a'),
(2, 1, 'b'),
(3, 1, 'c'),
(4, 0, 'd'),
(5, 4, 'e'),
(6, 5, 'f'),
(7, 4, 'g')
)

class Node:
def __init__(self, n, s):
self.id = n
self.title = s
self.children = []

treeMap = {}
Root = Node(0, "Root")
treeMap[Root.id] = Root
for element in els:
nodeId, parentId, title = element
if not nodeId in treeMap:
treeMap[nodeId] = Node(nodeId, title)
else:
treeMap[nodeId].id = nodeId
treeMap[nodeId].title = title

if not parentId in treeMap:
treeMap[parentId] = Node(0, '')
treeMap[parentId].children.append(treeMap[nodeId])

def print_map(node, lvl=0):
for n in node.children:
print ' ' * lvl + n.title
if len(n.children) > 0:
print_map(n, lvl+1)

print_map(Root)

"""
Output:
a
b
c
d
e
f
g
"""
This works well for my purposes because I want to be able to go back and refer to an element by id without having to write the code to traverse the tree and find it. Keeping a copy of a tree structure and keeping a reference to each element in a dictionary, I get the best of both worlds. Deletions are difficult since I'm not keeping track of parent nodes. But, since the use case is a menu on an ASP.NET page that rebuilds on every load, I'm not storing a copy of the tree in memory long-term (i.e., deletions and insertions are irrelevant).

Unfortunately this is just a sketch to wrap my brain around the idea. In real life I had to implement it in VB.NET. (see http://pastebin.com/f8e9c672)

blog comments powered by Disqus

Subscribe Now

About Me

My Photo
Baltimore, MD, United States
Husband and father, software developer in Baltimore, MD. http://adambachman.org