[Tutor] Of integers, relations and trees

Andrei project5 at redrival.net
Sat Dec 9 11:55:09 CET 2006


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





More information about the Tutor mailing list