python - 从二叉搜索树创建列表

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)

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