0

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

The output using this code is:

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

And I want this output:

Adams, A (1991) Loves football

Marlow, C (1996) Loves cricket

Smith, I (1994) Does not play sports
Hassan
  • 21
  • 9
  • It is not understandable what you are trying to achieve, you only specify what is happening in the code and that you don't want this certain type of output, what do you mean by "you do not want this" - then what do you want?. What is the question of this post then? Please provide a sample code and a desired solution. – CodeCop May 03 '20 at 11:20
  • The "traverse a binary search tree in alphabetical order" part of the assignments wants you to do an in-order traversal (https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR)). You seem to have solved that part. Now it is just about producing the output in the form the assignment asks. – user7610 May 03 '20 at 12:11
  • Hello thank you for your reply , do you know how I can do this so outputBibliography(self): can call it? – Hassan May 03 '20 at 12:19
  • Well, you would return the string, instead of printing it. So something like this: ```def outputBibliography(self): return '\n\n'.join(self.traverse(self.bibtree.root))``` – user7610 May 03 '20 at 12:33
  • Thank you for your quick response, i cannot touch the def outputBibliography(self), only the def traverse(self, aNode): so should i add return '\n\n'.join(self.traverse(self.bibtree.root)) to it then ? – Hassan May 03 '20 at 13:37
  • You do want to return a list from `traverse`, though, because appending to a list has constant amortized time complexity, whereas appending to a string in python is a linear operation, giving rise to O^2 loops. This is because Python strings are immutable, as described e.g. https://stackoverflow.com/questions/34008010/is-the-time-complexity-of-iterative-string-append-actually-on2-or-on – user7610 May 04 '20 at 08:46
  • If you go for the solution that uses a string directly, instead of a list, it should be probably fine. Maybe add a comment that you thought about the inefficiency of concatenating strings in a loop (or in a recursive function, in your case). – user7610 May 04 '20 at 08:47
  • Does this answer your question? [Python string concatenation Idiom. Need Clarification.](https://stackoverflow.com/questions/1967723/python-string-concatenation-idiom-need-clarification) – MisterMiyagi May 04 '20 at 16:18

2 Answers2

1

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

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.

user7610
  • 25,267
  • 15
  • 124
  • 150
  • thank you for this solution, you seem to know alot. Can i ask you, if i was to add a duplicate key what adjustment would i need to make to addReference and removeReference functions so i can get a general understanding. – Hassan May 04 '20 at 16:01
  • You aren't supposed to ask "large" followup questions on SO. Anyways, it depends on how your BST class is written. Both `addReference` and `removeReference` essentially just delegate to `addNode` and `deleteNode` in BST. I'm reading more on the homework questions policy now.. https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions – user7610 May 04 '20 at 16:20
  • Best way to answer the followup question would be to try implementing it. Then you will see what needs to be done to make everything work. Should `removeReference` remove all the duplicate keys, or just the "first" one? Do you want to have some ordering between the duplicate keys, such as that they should be printed in the order of insertion? (Stable sorting.) If so, you have to think it through when implementing it so that this property is met. – user7610 May 04 '20 at 16:25
  • ok thank you for your help! im going to crack on and try solving this, if you got any good links let me know as information on the web is all different. – Hassan May 04 '20 at 16:35
  • What do you want to help with? General Python questions, programming tricks (how to work with recursive functions, for example), or data structures, Computer Science stuff? For general Python questions, what helped me was reading the Python tutorial "from cover to cover" . It is part of Python documentation (https://docs.python.org/3/) the link Tutorial. Direct link here https://docs.python.org/3/tutorial/index.html. It is long, but it is quite helpful. I head good things about https://learnpythonthehardway.org/book/ (free on the web) but I did not read it myself. – user7610 May 04 '20 at 18:01
  • yeah general python question, when i understand how you get the answer is how i lean better. come look at this question https://stackoverflow.com/q/61598888/11302234 – Hassan May 04 '20 at 18:18
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/213119/discussion-between-user7610-and-hassan). Can you use the SO chat? I am not sure if there are reputation limits to access it. Let's go there. – user7610 May 04 '20 at 19:30
0

You are almost there. Your traverse method produces a list of the desired lines. The only thing that is remaining is to turn that list into a single string where the lines are separated by '\n\n', that is, one '\n' to terminate the current line and another '\n' to give a blank line.

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

This now prints the output in the form you want it.

user7610
  • 25,267
  • 15
  • 124
  • 150