[Tutor] Help with objects

[Danny Yoo]

On Mon, 21 Nov 2005, Vincent Wan wrote:

> Thank you bob. I fixed the errors where I tried to index a dictionary
> with name() so so that they say name[]
>
> >> Beyond the error I'm still not sure I understand how to make and use
> >> a tree data structure using objects.
>
> There is a new error as well
>
> Traceback (most recent call last):
>    File "/Users/Wally/obj_tree1.py", line 28, in -toplevel-
>      currentTree = Tree()
>    File "/Users/Wally/obj_tree1.py", line 21, in __init__
>      nodeList[0] = Tree.Node(0)    # adds a root node 0 to the tree
> NameError: global name 'nodeList' is not defined


Hi Vincent,

You may want to look at places in your code where assigning nodeList does
appear to work.  For example, Node.__init__ appears to do:

    Tree.nodeList[self.name] = self


Check the line that's raising an error:

    nodeList[0] = Tree.Node(0)

as well as the content of the error message:

    NameError: global name 'nodeList' is not defined

Do you understand what the error message is trying to say?



You may also want to go through a formal tutorial that talks about data
structures like trees.  For example, How to Think like a Computer
Scientist has a whole chapter on trees:

    http://www.ibiblio.org/obp/thinkCSpy/chap20.htm

Although this concentrates on binary trees, the examples can be adjusted
to do an arbitrary tree of any branching width.  Rather than have each
node have a link to their 'left' and 'right' children, we can do links to
the "first child" and "next sibling".

The implementation you have should be fine, but I did promise you an
alternative implementation of trees.  As a quick and dirty example of what
this might look like, I'll strip it down so that there's minimal class
stuff.

######
class Node:
    def __init__(self, id):
        self.id = id
        self.firstChild = None
        self.nextSibling = None

def addChild(node, childId):
    child = Node(childId)
    child.nextSibling = node.firstChild
    node.firstChild = child
    return child
######

(The only reason I'm making a class definition at all is just to treat it
as a data structure with labeled attributes.  But everything else I write
here will be a function, since you probably have a good foundation with
them.)


Once we have something like this, then if we wanted to represent a node
with three children:

                1
               /|\
              / | \
             2  3  4

then we can do something like this:

######
>>> node1 = Node(1)
>>> addChild(node1, 2)
<__main__.Node instance at 0x733a0>
>>> addChild(node1, 3)
<__main__.Node instance at 0x73620>
>>> addChild(node1, 4)
<__main__.Node instance at 0x737d8>
######


Does this work?  Let's inspect what we have so far:

######
>>> node1.firstChild
<__main__.Node instance at 0x73558>
>>> node1.firstChild.id
4
>>> node1.firstChild.nextSibling.id
3
>>> node1.firstChild.nextSibling.nextSibling.id
2
>>>
>>> node1.firstChild.nextSibling.nextSibling.nextSibling.id
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
AttributeError: 'NoneType' object has no attribute 'id'
######

There they are.  And, of course, if we jump off the list, as in the last
example, we'll get an error.  We should be careful to look before jumping.


If it seems awkward to go through the list of children like this, we can
abstract away the linked list traversal by writing a helper function, like
this:

######
def children(node):
    """Returns the children of a node."""
    children = []
    child = node.firstChild
    while child != None:
        children.append(child)
        child = child.nextSibling
    return children
######


And now we can more easily see that node1 has three children:

######
>>> for child in children(node1):
...    print child.id
...
4
3
2
######


The staticmethods and nested classes that you have now seem slightly
over-the-top to me, which is why I'm trying to counterbalance that with
the simplest generalized tree example I can think of.  *grin*

I guess I'm trying to say: if you're doing tree stuff, you don't even need
to use much sophisticated class stuff --- I think that simple functions
should suffice at the moment.

Good luck to you.