Creating a List from a Binary Search Tree

I'm trying to make a list of all items in a binary search tree. I understand the recursion but I don't know how to make it return each value and then append it into a list. I want to create a function called makeList() that will return a list of all the items in my tree. All the functions in my programs work except the makeList() function and are included to make sure everyone understands the basic structure of how I set up my tree.

class Node(object):
    def __init__(self, data):
        self.data = data
        self.lChild = None
        self.rChild = None

class Tree(object):
    def __init__(self):
        self.root = None

    def __str__(self):
        current = self.root

    def isEmpty(self):
        if self.root == None:
            return True
        else:
            return False

    def insert (self, item):
        newNode = Node (item)
        current = self.root
        parent = self.root

        if self.root == None:
            self.root = newNode
        else:
            while current != None:
                parent = current
                if item < current.data:
                    current = current.lChild
                else:
                    current = current.rChild

            if item < parent.data:
                parent.lChild = newNode
            else:
                parent.rChild = newNode

    def inOrder(self, aNode):
        if aNode == None:
            pass
        if aNode != None:
            self.inOrder(aNode.lChild)
            print aNode.data
            self.inOrder(aNode.rChild)

    def makeList(self, aNode):
        a = []
        self.inOrder(aNode)
        a += [aNode.data]
        print a

n = Tree()
for i in [4,7,2,9,1]:
    n.insert(i)

n.makeList(n.root)

Looking at my makeList() function I can see why it doesn't work but I don't know how to make it work.

EDIT

Ok, I got it! And I even got two answers which are:

def makeList(self, aNode, a = []):
    if aNode != None:
        self.makeList(aNode.lChild, a)
        a += [aNode.data]
        self.makeList(aNode.rChild, a)
    return a

and

def makeList2(self, aNode):
    if aNode is None:
        return []
    return self.开发者_如何转开发makeList2(aNode.lChild) + [aNode.data] + self.makeList2(aNode.rChild)

And looking back I can see that I do not understand recursion very well so it's time to hit the books! Anyone have any good resources on recursion?

Another question, so say I call my makeList() function. When Python goes through makeList(), when it gets to the self.makeList(aNode.lChild, a) does it begin running the function again while it's still finishing up the makeList() function or does everything stop and it just starts over with it's new aNode?

I hope that makes sense.

---

You're so close! makeList can be pretty simple:

def makeList(self, aNode):
    if aNode is None:
        # Stop recursing here
        return []
    return self.makeList(aNode.lChild) + [aNode.data] + self.makeList(aNode.rChild)

Basically, make sure you're not trying to recurse past empty nodes. Then return the list of the left tree, the current node, and the list of the right tree.

---

inOrder prints things but does not return anything, so it's useless for building a list. You need a way to return each node in order. This may be something that your class hasn't covered yet, but check out the yield command.

---

The basic idea is something like this:

def makeList(self):
    return self.lChild.makeList() + [self.data] + self.rChild.makeList()

See how it is essentially the same thing as inOrder?

You have a different structure in your program that makes it a bit harder to implement, but the basic idea is the same.