如何按字母顺序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)

当我进行测试时，下面的功能无法正常工作，需要 help.It returns 它作为此括号 [ ] 中的列表，我不想要这个。我也想要一个空行，但这也没有发生。我不确定我做错了什么，如果你能给我一些建议，这会有所帮助。

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\n')
          res = res + self.traverse(aNode.rightChild)
        return res

使用此代码的输出是：

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

我想要这个输出：

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))

这会以您想要的形式打印输出。

Answer 2

并且您无论如何都在连接列表，如 res + self.traverse(aNode.rightChild) 中那样。好吧，别介意我之前对此的评论，即使有列表，你也会得到 O^2，因为你正在复制它们。就这样做

def traverse(self, aNode):
    res = ""
    if aNode:
        res = self.traverse(aNode.leftChild)
        res += aNode.key + ' ' + aNode.payload + '\n\n'
        res += self.traverse(aNode.rightChild)
    return res

这最终会在最后一个引用之后为您提供一个空行，因此它是作业所说内容的更字面的实现：“...在每个引用之后都有一个空行...”。 join() 只会在引用之间插入换行符，而不是在最后一个引用之后。

如何按字母顺序python遍历一棵二叉搜索树？

How to traverse a binary search tree in alphabetical order python?

python

function

binary-search-tree

traversal