从二进制搜索T创建列表

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)

基本上，确保不要尝试递归到空节点。然后返回左树列表、当前节点和右树列表。

Answer 2

inOrder打印内容，但不返回任何内容，因此它对于构建列表毫无用处。您需要一种方法来按顺序返回每个节点。这可能是您的类尚未涵盖的内容，但请查看yield命令。

Answer 3

基本思想是这样的：

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

你看它和inOrder本质上是一样的吗？

你的程序有一个不同的结构，这使得它有点难以实现，但基本思想是一样的。