如何遍历二进制搜索树中的字母顺序python? [英] How to traverse a binary search tree in alphabetical order python?

问题描述

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

I need your help or if you can give me advice. I'm really struggling and some help would be perfect, so this is what I got so far;

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)

当我进行测试时，以下功能不起作用，需要帮助.它将作为列表返回到此括号[]中，我不希望这样做.我也想要一个空白行，也不会发生这种情况.我不确定我在做什么错，如果您可以给我一些建议，这会有所帮助.

When I do the test the below function is not working and need help.It returns it as a list in this bracket [ ] and I do not want this. I also want a blank line and this does not happen either. I'm not to sure what I'm doing wrong, if you can give me some advise this will be helpful.

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

推荐答案

您仍然要串联列表，如res + self.traverse(aNode.rightChild)所示.好的，不用管我以前对此的评论，即使有列表，也可以在其中得到O ^ 2，因为您正在全部复制它们.这样做

And you are concatenating lists anyways, as in res + self.traverse(aNode.rightChild). Ok, never mind my previous comments about this, you get O^2 there even with lists, because you are copying them all over. Just do this

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()只会在引用之间插入换行符，而不能在最后一个之后插入.

This ends up giving you an empty line after the last reference, so it is more literal implementation of what the assignment says: "... with an empty line after each reference ...". That join() would only insert the newlines between references, and not after the last one.

这篇关于如何遍历二进制搜索树中的字母顺序python?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！