Python Class Method Help

[blackrobe]

Hi all,

I'm required to implement a method for a "TernarySearchTree" object/class.
Basically, a Ternary search tree is just like a binary tree except it has three children instead of two.

Ternary Search Tree could only manipulate it's root.
Now the method should create and return an alphabetically sorted list consisting of exactly the strings represented in the ternary search tree. for example it should return something like:

You could check this link to view the shape of the tree:
http://www.ddj.com/showArticle.jhtml?documentID=ddj9804a&pgno=4

Now my code gives this result: (for some reason)...

My code:

def collect_sorted (self, word = '', list_words = []):
    if self.root.centre.splitchar == '$':
      word+=self.root.splitchar
      list_words.append(word)
      return
    if self.root.left:
      pointer = self.root
      self.root = self.root.left
      self.collect_sorted(word)
      self.root = pointer
    if self.root.centre.splitchar != '$':
      pointer = self.root
      word += self.root.splitchar
      self.root = self.root.centre
      self.collect_sorted(word)
    if self.root.right:
      pointer = self.root
      self.root = self.root.right
      self.collect_sorted(word)
      self.root = pointer
    return list_words

I would really appreciate it if someone could help me figure out what's wrong..

Thanks a lot,
Blackrobe =)

[tyincali]

I don't think I can properly walk through this without seeing more. What does the input data look like? How is it loaded?

[blackrobe]

what does the initial call to this look like? I can't walk through it unless I know what data is being passed to it.

It's:

class TernarySearchTree:

  def __init__ (self):
    self.root = None

  def has_key (self, s):
    if self.root:
      return self.root.has_key (s + "$")
    else:
      return False

  def has_key2 (self, s):
    if self.root:
      return self.root.has_key2 (s + "$")
    else:
      return False

  def put (self, s):
    if self.root:
      self.root.put (s + "$")
    else:
      self.root = TreeNode (None, None, None, s[0])
      self.root.put (s + "$")

if __name__ == '__main__':
  tst = TernarySearchTree()
  words = ['is','be','on','in','as','of','at','by','he','or','to','it']
  for letter in words:
    tst.put(letter)
  print tst.collect_sorted()

[danny'sweb]

Hey - I just finished working on the same assignment. Sadly, that means that I can't just give you the answer. But if you're still having trouble with it, here's what I can say:

You've got the right idea. But there's no need to have 2 self.root.centre if statements - they can be integrated. And remember: the order in which you traverse the tree is important. You need to perform an inorder traversal to get the strings out in alphabetical order.

One other thing that struck me in your code - your word variable assignments might cause hiccups. Better to store the strings you're building from each branch in a temp variable so as to avoid overlapping (play around with the order of your if statements and you'll see what I mean).

Good luck!

[danny'sweb]

One more hint: see what happens if you remove the return from your if self.root.centre.splitchar == '$' statement.