[Tutor] building non binary trees CLARIFIED

Vincent Wan wan at walrus.us
Fri Nov 18 03:41:29 CET 2005

Let me try to clarify my problem.

I would like to have a tree data structure with trees whose nodes  
could have an arbitrary
number of descendants and that I could iterate over by the names of  

this is the first time I've used objects.

I tried to model my code on a binary tree data structure Roel  
Schroeven wrote in reply to an earlier post of mine


but I don't understand what's happening in his code on the line  
commented # what's happening here

         class Tree(object):
             class Node(object):
                 def __init__(self, linage, left=None, right=None):
                     self.linage = linage
                     self.left = left
                     self.right = right
             def __init__(self, rootlinage):
                 self.rootnode = Tree.Node(rootlinage)
                 self.linagetonode = {rootlinage: self.rootnode}  #  
what's happening here
             def AddBranch(self, linage, newlinage):
                 node = self.linagetonode[linage]
                 left = Tree.Node(linage)
                 right = Tree.Node(newlinage)
                 node.left = left
                 node.right = right
                 self.linagetonode[linage] = left
                 self.linagetonode[newlinage] = right

my code seems to barf because when I call Tree's AddBranch method I'm  
not telling
it which node to add to. I don't know how to go from the name of a  
node (here a integer) to reference to
the node with that name to pass to AddBranch.

my code

import random

# constants that control the simulation
NUMBER_REPS = 10        # run's the simulation
MAX_LINAGES = 10        # number of species in each run

class Tree(object):
     numLinages = 0
     class Node(object):
         def __init__(self, name):
             self.name = name
             self.alive = True
             self.descendents = []
             Tree.numLinages += 1
     def __init__(self):
         self.rootnode = Tree.Node(0)
     def AddBranch(self, linage, offspring):
         new = Tree.Node(offspring)
     def NumLinages(  ):
         return Tree.numLinages
     NumLinages = staticmethod(NumLinages)

currentTree = Tree()
print Tree.NumLinages()

for i in range(NUMBER_REPS):
     j = 0
     while j <= currentTree.NumLinages():
         if random.random() >= BRANCHING_PROBABILITY:
             currentTree.AddBranch(j, currentTree.NumLinages() + 1)
         j += 1

Vincent Wan

PhD Candidate
Committee on the Conceptual and Historical Studies of Science
University of Chicago

PO Box 73727
Fairbanks, AK 99707

wan AT walrus DOT us (change CAPS to @ and . )

More information about the Tutor mailing list