Tor Hildrum wrote:
I have this problem which I thought would be trivial, but I can't
seem to figure out a decent way to do it.
Say I have the following file:
10
-100
snip
-108
--1080
snip
12
snip
20
In lack of a better explanation, here is how it works:
A level in the tree follows the following:
x * 10^level
x * 10^1 belongs to level 1 in the three
x * 10^2 belongs to level 2 in the three.
etc.
Here's a different way to look at it: the level in the tree is
determined by the length of the string representation of the node. 2
long - level 1. 3 long - level 2. etc.
I decided to make this pretty straightforward so I wrote a Node class
and a Tree class.
Are you sure you need a Tree class? The Node class itself may have all
the facilities needed to manage an entire tree. The tree is then
represented by a 'root' node. You'd then have:
- root
- 10
- 103
- 105
- 12
etc.
A Node has a key which is an integer, as well as some additional
information that isn't relevant to the structure. It also has a link
to it's sibling, which is the next node on the same level. And a link
to it's first child.
A different way to implement this is for each node to have a (sorted)
list of children and potentially a link to its parent. The story then
looks like this:
- root with the following children
- 10 (with parent = root) with the following children:
- 100
- 108
- 12 (with parent = root)
etc.
You then do not insert siblings, you add children (not tested, but the
intention is what counts):
class Node(object):
def __init__(self, name):
self.Name = name
self.Parent = None
self.Children = []
def addChild(self, newname):
Tries to add the node as a newNode. Returns True
if successful, False otherwise.
# check if the node is a (sub)child
if newname[:len(self.Name)] self.Name:
return False
# check if it is a direct descendant
if len(newname) == len(self.Name) + 1:
newnode = Node(newname)
newnode.Parent = self
self.Children.append(newnode)
self.Children.sort()
return True
else: # not a direct descendant - add to one of the children
for child in self.Children:
if child.addChild(newname):
return True
# if we arrive here, it means that there's a missing level in
the hierarchy - add it
self.addChild(newname[:len(newname)-1])
return self.addChild(newname)
def show(self, indentation=0):
print ' ' * indentation, '-', self.Name
for child in self.Children:
child.show(indentation + 2)
def __cmp__(self, othernode):
Get sort() to work properly.
return cmp(self.Name, othernode.Name)
def hasChildren(self):
return len(self.Children) 0
def hasSiblings(self):
return (self.Parent None) and (len(self.Parent.Children) 1)
root = Node('')
root.addChild('10')
root.addChild('12')
root.addChild('0')
root.addChild('20')
root.addChild('108')
root.addChild('5')
root.addChild('678')
root.show()
This implementation will not handle the dot-style leaves properly,
you'll need some extra logic for that. It will however 'fill in the
blanks', so you can add node '678' without adding nodes '6' and '67'
first and auto-sort the nodes.
How do I know if I have a sibling or a child?
Simple, I just check the length:
-
if( len(str(node1[key])) == len(str(node2[key])) ):
-
If the length, amount of integers, is the same, they are siblings.
With the alternative representation presented, it's more comfortable:
- has child: len(self.Children) 0
- has sibling: (self.Parent None) and (len(self.Parent.Children) 1)
How do I determine that 2080 is not a child of 10. Or how do i determine
that 536798 is not a child of 536780? And how do I determine that it is a
child?
See my code: just manipulate them as strings and it's suddenly very
easy. Same length and the first (length - 1) characters are the same -
siblings. Different length: take the shortest node name; if the other
node name starts with that string, it's a child, otherwise they're
unrelated.
I can't seem to rack my brains around a solution for this. Maybe it's
my tree-structure that is making this more complex than it should be?
Hierarchies are easier if you look at them as families: it's easier to
ask a parent how many children it has, than it is to ask one of the
siblings if there is any sibling younger than it, then ask that younger
sibling if it has any younger siblings, etc.
Yours,
Andrei
___
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
