python - strange result in tree implementation

Question

While writing some scripts in python, I wrote a simple class tree structure. After testing it, I got a strange but interesting result;

Suppose that we implement a simple tree such that each node has one child. Then, we may be able to implement it like this:

class node_1(object):
    def __init__(self, data = 0, child = None):
        self.data = data
        self.child = child

    def append(self, child):
        self.child = child

    def __str__(self):
        return '(box %s)' % str(self.data)

    def __repr__(self):
        return self.__str__()

When we execute the following code:

root_1 = node_1(0)
root_1.append(node_1(1))
root_1.child.append(node_1(2))

print root_1, root_1.child, root_1.child.child

we get the following result, which we expected:

(box 0) (box 1) (box 2)

Now let's suppose that each node can have multiple childs; if we implement it like the following code:

class node_2(object):
    def __init__(self, data = 0, childs = []):
        self.data = data
        self.childs = childs

    def append(self, *childs):
        map(self.childs.append, childs)

    def __str__(self):
        return '(box %s)' % str(self.data)

    def __repr__(self):
        return self.__str__()

Then the code

root_2 = node_2(0)
root_2.append(node_2(1), node_2(2))
root_2.childs[0].append(node_2(3), node_2(4))

print root_2, root_2.childs, root_2.childs[0].childs

outputs

(box 0) [(box 1), (box 2), (box 3), (box 4)] [(box 1), (box 2), (box 3), (box 4)]

, instead of

(box 0) [(box 1), (box 2)] [(box 3), (box 4)]

I'm guessing that this is related to the reference of items in a iterable object, but I can't figure out the (precise) reason why the child nodes' self.childs contains not only their childs, but also sibling nodes and even parent nodes. Could you please help me to understand why this result appeared?

(full code : https://github.com/Avantgarde95/share/blob/master/btest.py )

[Solved]

Thanks to thefourtheye and the link he provided, I could understand that the problem was occurred by 'childs = []' statement. According to the link, default argument is (re-)evaluated only when python meets the 'def' keyword; so if I set the default argument 'childs' to a mutable object (such as list), after the first call of self.append, all self.childs of nodes will point the same object.

The following code now works well:

class node(object):
    def __init__(self, data = 0, childs = None):
        self.data = data

        if childs is None:
            self.childs = []
        else:
            self.childs = child

    def append(self, *childs):
        map(self.childs.append, childs)

    def __str__(self):
        return '(box %s)' % str(self.data)

    def __repr__(self):
        return self.__str__()

Executing

root = node(0)
root.append(node(1), node(2))
root.childs[0].append(node(3), node(4))

print root, root.childs, root.childs[0].childs

gives

(box 0) [(box 1) (box 2)] [(box 3) (box 4)]

python - strange result in tree implementation

0 Answers0