1

So Python doesn't really do this. I have a class called tree, it's a binary tree type.

class Tree(object):
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

    def filler(self, lista, tree):
        tree = Tree()
        nr = len(lista)
        nr //= 2
        if len(lista) == 0:
            return
        if len(lista) == 1:
            tree.data = lista[0]
            return
        tree.data = lista[nr]
        self.filler(lista[:nr], tree.left)
        self.filler(lista[nr:], tree.right)

Function filler() transforms a list into a binary tree. I try calling it like this:

tr = Tree()
tr2 = Tree()
l = self.ctrler.Backtrack(self.ctrler.tsk, 0) -- some list
tr.filler(l, tr2)
print(tr2.data)

The result is None. filler() doesn't do anything. Can I do anything about this? Can I pass the tr2 object by reference? How can I transform a list into a binary tree if I can't pass it by reference?

Traceback without the instatiation of tree in the filler:

Traceback (most recent call last):
  File "D:/Projects/Python/AIExcavator/src/ui.py", line 75, in <module>
    uier.inter()
  File "D:/Projects/Python/AIExcavator/src/ui.py", line 63, in inter
    tr.filler(l, tr2)
  File "D:\Projects\Python\AIExcavator\src\Backtracking.py", line 79, in filler
    self.filler(lista[:nr], tree.left)
  File "D:\Projects\Python\AIExcavator\src\Backtracking.py", line 78, in filler
    tree.data = lista[nr]
AttributeError: 'NoneType' object has no attribute 'data'
Improve this question
1
  • It's a list of lists. I use recursion there. My recursion has to end when my list is done. I split my list in 2, left and right all the time to fill the binary tree. It works fine (Checked by printing the lenght of the passed lsit every time) but it doesn't fill the tr2 Commented Apr 1, 2016 at 19:12

2 Answers 2

Reset to default
3

filler is a little odd anyway, since it only needs self in order to make the recursive call. It's really an alternate constructor, making it more appropriate as a class method, something like

class Tree(object):

    def __init__(self, data=None, left=None, right=None):
        self.left = left
        self.right = right
        self.data = data

    # The former method filler()
    @classmethod
    def from_list(cls, lista):
        if lista:
            # All non-empty lists are the same.
            # Specifially, nr = 0 for a single-element list,
            # and lista[:nr] and lista[nr+1:] are empty lists
            # in the edge cases.
            nr = len(lista) // 2
            return cls(lista[nr],
                        cls.from_list(lista[:nr]),
                        cls.from_list(lista[nr+1:]))
        else:
            return None

tree = Tree.from_list([1,2,3,4,5,6])

The benefit of using a class method is that you can define a subclass of Tree without having to redefine from_list. Consider

class BackwardsTree(Tree):
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        # Swap the left and right subtrees
        self.right = left
        self.left = right

bt = BackwardsTree.from_list([1,2,3,4,5,6])

Although BackwardsTree.from_list resolves to Tree.from_list because you didn't override the function, the return value will still be an instance of BackwardsTree, not Tree, because you used cls to create each (sub)tree, instead of hardcoding Tree inside the method.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

cls is whatever class actually calls the method. With Tree.from_list(...), it's Tree. With SomeSubclassOfTree.from_list(...), it's SomeSubclassOfTree.
Ok it's the first time I see this. So I don't need Tree to call the class anymore or wut? Can I just replace cls with self?
No, the first argument to a class method is conventionally called cls. Don't use self.
And what's with the first return? That return tree(...). It's unresolved reference
That was a typo; it's fixed now to use return cls(...).
1

You write

tr.filler(l, tr2)

but in filler, you don't use tr2, as you erase it with a new tree object.

def filler(self, lista, tree):
    tree = Tree()

Also, as pointed out in comments,

self.filler(lista[:nr], tree.left)
self.filler(lista[nr:], tree.right)

is wrong because you pass tree.left and tree.right, both being None while filler expects a tree object, not None.

Regarding passing by reference, you should read about mutables in Python. TL;DR: If you pass tr2 to filler and modify it in filler, it will be modified indeed.

Improve this answer

6 Comments

If I don't do that, it says that tree.data doesn't exist because tree is of value None... what should I do?
It shouldn't say that. Please post full code + trace back showing the error and the line it happens.
It's the last 2 lines in filler, where he passes the freshly created Tree instances left and right attributes, that are None, I think.
I added the traceback
Ok so then what should I change? Before calling self.filler(lista[nr]... ) so initialize tree.left and tree.right with Tree() ?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.