如何遍历按字母顺序排列的二进制搜索树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='nn')
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 + 'nn')
res = res + self.traverse(aNode.rightChild)
return res

使用此代码的输出为：

['Adams, A (1991) Loves footballnn', 'Marlow, C (1996) Loves cricketnn', 'Smith, I (1994) Does not play sportsnn']

我想要这个输出：

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

Answer 1

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

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

这最终会在最后一个引用之后给你一个空行，所以它更像是赋值所说的："…每个引用之后都有一个空线…"的字面实现。join()只会在引用之间插入换行符，而不会在最后一次引用之后插入。

Answer 2

您就快到了。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('nn'.join(tmp))

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