[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
nodes
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
http://mail.python.org/pipermail/tutor/2005-November/043214.html
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
BRANCHING_PROBABILITY = 0.5
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)
self.descendents.append(new)
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