[Tutor] btree problems

Justin Sheehy dworkin@ccs.neu.edu
14 Mar 2000 17:51:05 -0500

Bruce Sass <bsass@freenet.edmonton.ab.ca> writes:

> Traceback (innermost last):
>   File "/home/bsass/usr/src/python/tree-test2.py", line 43, in ?
>     print "  tree.entry =", tree.entry
> AttributeError: entry

Well, the error is telling you what's wrong: "tree" has no attribute
named "entry".  It is an instance of btree, and your btree classes do
not have variables by that name.  This is probably caused due to a
confusion between trees and nodes.

Personally, I would have used a single class to encompass the
functionality of your "node" and "btree" classes, but that may not
really be necessary to solve your problem.

Your _InsertTree method is also flawed.  It assigns the new node to
the local variable "branch" instead of the relevant instance variable.
While "branch" may have been a reference to the same thing as the
instance variable you wanted to assign to, the assignment statement
merely reassigns what "branch" refers to without looking at its
previous value.

Here is a version of that code that has been modified to take those
changes into effect.  It still has some imperfections, but it
illustrates potential solutions to the problems I note above.


class datapkg:
    def __init__(self, key=None, data=None):
        self.key = key
        self.data = data

class btree:
    def __init__(self):
        self.entry = None
        self.left = None
        self.right = None

    def insert(self, newdata):
        if self.entry == None:
            self.entry = datapkg(newdata.key, newdata.data)
        elif newnode.entry.key < self.entry.key:
            if self.left == None:
                self.left = btree()
            if self.right == None:
                self.right = btree()

tree = btree()
print "Created a tree: tree =", tree

n = datapkg()
n.key = "first"
n.data = ['some', 'data']
print "Created a datapkg: n =", n
print "  n.key =", n.key
print "  n.data =", n.data

print "Inserted the datapkg into the tree:"
print "  tree =", tree
print "  tree.entry =", tree.entry
print "  tree.entry.key = ", tree.entry.key