如何以字母顺序python遍历二叉搜索树？

Question

我需要您的帮助，或者如果您可以给我建议。我真的很努力，有些帮助会是完美的，所以这是我到目前为止所得到的；

import BST, TreeNode

class Bibliography:

def __init__(self):
    self.bibtree = BST()

def getReference(self,key):
    """Return the reference for the key, if it exists, otherwise None."""
    theValue = self.bibtree.retrieveKey(key,self.bibtree.root)
    if theValue == None:
        return None
    else:
        return theValue.payload

def addReference(self, key, value):
    """Add the reference represented by key and value.

    Assume the key does not exist in the bibliography.
    """
    self.bibtree.insertNode(key, value)

def removeReference(self, key):
    """Remove the reference with this key.

    Assume the key exists in the bibliography.
    """
    self.bibtree.deleteNode(key)

def outputBibliography(self):
    """Return a string with all references in alphabetical order.

    There must be an empty line after each reference
    """
    return self.traverse(self.bibtree.root)

def traverse(self, aNode):
    """Return a string with the references in the subtree rooted at aNode.

    The references should be ordered alphabetically,
    with an empty line after each reference
    and a space between each key and its value. See the test file.
    """
    if aNode:
      self.traverse(aNode.leftChild)
        return str(aNode.key, aNode.payload, end='\n\n')
      self.traverse(aNode.right)

[当我进行测试时，以下功能无法正常工作，需要帮​​助。它以括号[]的列表形式返回它，我不希望这样做。我也想要一个空白行，也不会发生这种情况。我不确定我在做什么错，如果您可以给我一些建议，这会有所帮助。

def traverse(self, aNode):
    """Return a string with the references in the subtree rooted at aNode.

    The references should be ordered alphabetically,
    with an empty line after each reference
    and a space between each key and its value. See the test file.
    """
        res = []
        if aNode:
          res = self.traverse(aNode.leftChild)
          res.append(aNode.key + ' ' + aNode.payload + ' \n ')
          res = res + self.traverse(aNode.rightChild)
        return res

使用此代码的输出是：

['Adams, A (1991) Loves football', 'Marlow, C (1996) Loves cricket', 'Smith, I (1994) Does not play sports']

并且我想要此输出：

Adams, A (1991) Loves football

Marlow, C (1996) Loves cricket

Smith, I (1994) Does not play sports

Answer 1

您快到了。您的traverse方法生成所需行的列表。剩下的唯一事情就是将列表转换为单个字符串，其中的行用'\ n \ n'分隔，即，一个'\ n'终止当前行，另一个'\ n'给出一个空行。

tmp = tree.traverse(tree.root)  # tmp now contains the list ['Adams, A (1991) Loves football', 'Marlow, C (1996) Loves cricket', ...
print '\n\n'.join(tmp)

现在将以所需的形式打印输出。