从二叉搜索树创建列表

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

基本的想法是这样的：

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

你看，这其实和 inOrder 是一回事，对吧？

虽然你程序里的结构有点不同，这让实现起来稍微复杂一些，但基本的思路是一样的。

Answer 2

inOrder这个函数只是打印东西，但不返回任何结果，所以它在构建列表时没什么用。你需要一种方法来返回每个节点，按顺序返回。这可能是你的类还没有讲到的内容，不过可以看看yield这个命令。

Answer 3

你已经很接近了！makeList 可以写得很简单：

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

基本上，要确保你没有试图在空节点上继续递归。然后返回左边树的列表、当前节点和右边树的列表。