从二叉搜索树创建列表

Question

我正在尝试列出二叉搜索树中的所有项目。我理解递归，但我不知道如何让它返回每个值，然后将其附加到列表中。我想创建一个调用的函数makeList()，该函数将返回我的树中所有项目的列表。我的程序中的所有函数都可以工作，除了makeList()函数，并且包含在内是为了确保每个人都理解我如何设置树的基本结构。

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)

查看我的makeList()函数，我可以明白为什么它不起作用，但我不知道如何使它起作用。

编辑

好，我知道了！我什至得到了两个答案，它们是：

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

和

def makeList2(self, aNode):
    if aNode is None:
        return []
    return self.makeList2(aNode.lChild) + [aNode.data] + self.makeList2(aNode.rChild)

回顾过去，我可以看到我不太了解递归，所以是时候看看书了！任何人都有关于递归的好资源？

另一个问题，所以说我调用我的makeList()函数。当 Python 通过时makeList()，当它到达时，它self.makeList(aNode.lChild, a)是在它仍在完成函数时再次开始运行该函数，还是makeList()一切都停止了，它只是从新开始aNode？

我希望这是有道理的。

Answer 1

你太接近了！makeList 可以非常简单：

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

基本上，确保您没有尝试递归过去的空节点。然后返回左树的列表、当前节点和右树的列表。