I have created two classes, STNode and StringTree. In my class StringTree, I am having problems with the last three functions (count, max and remove). I have added comments to show what I would like my code to do that it currently is not. Ideally, I would like to only make changes to my StringTree class as I am perfectly fine with STNode.
To further explain the purpose of my code: Each node has three children: left, right and forward;
- each node contains a character (the data of the node) and a non-negative integer (the multiplicity of the stored data).
- the left child of a node, if it exists, contains a character that is smaller (alphabetically) than the character of the node
- the right child of a node, if it exists, contains a character that is greater than the character of the node
Code:
class STNode:
def __init__(self,d,l,m,r):
self.data = d
self.left = l
self.right = r
self.next = m
self.mult = 0 #multiplicity to show end of word
# prints the node and all its children in a string
def __str__(self):
st = "(" str(self.data) ", " str(self.mult) ") -> ["
if self.left != None:
st = str(self.left)
else: st = "None"
if self.next != None:
st = ", " str(self.next)
else: st = ", None"
if self.right != None:
st = ", " str(self.right)
else: st = ", None"
return st "]"
class StringTree:
def __init__(self):
self.root = None
self.size = 0
def __str__(self):
return str(self.root)
def add(self,st):
if st == "":
return None
if self.root == None:
self.root = STNode(st[0],None,None,None)
ptr = self.root
for i in range(len(st)):
d = st[i]
while True:
if d == ptr.data:
break
elif d < ptr.data:
if ptr.left == None:
ptr.left = STNode(d,None,None,None)
ptr = ptr.left
else:
if ptr.right == None:
ptr.right = STNode(d,None,None,None)
ptr = ptr.right
if i < len(st)-1 and ptr.next == None:
ptr.next = STNode(st[i 1],None,None,None)
if i < len(st)-1:
ptr = ptr.next
ptr.mult = 1
self.size = 1
def addAll(self,A):
for x in A: self.add(x)
def printAll(self):
def printFrom(ptr,s):
if ptr == None: return
s0 = s ptr.data
for i in range(ptr.mult,0,-1): print(s0)
if ptr.left != None: printFrom(ptr.left,s)
if ptr.next != None: printFrom(ptr.next,s ptr.data)
if ptr.right != None: printFrom(ptr.right,s)
printFrom(self.root,"")
def _searchNode(self, ptr, d):
while ptr != None:
if d == ptr.data:
return ptr
if d < ptr.data:
ptr = ptr.left
else:
ptr = ptr.right
return None
# should return the number of times that string d is stored in the tree
def count(self, d):
ptr = self.root
count = 0
while ptr != None:
ptr = self._searchNode(ptr,d)
if ptr != None:
count = 1
ptr = ptr.right
return count
# should return the lexicographically largest string in the tree and if the tree is empty, should return None
def max(self):
last_seen_value = None
ptr = self.root
while ptr is not None:
last_seen_value = ptr.data
ptr = ptr.right
return last_seen_value
# should remove one occurrence of string i from the tree and return None
# if string i does not occur in the tree then it should return without changing the tree
# it should somehow update the size of the tree correctly
def remove(self, i):
if self.head == None:
return None
if i == '':
val = self.head.data
self.head = self.head.next
self.length -= 1
return val
else:
ptr = self.head
while i>1 and ptr.next != None:
ptr = ptr.next
i -= 1
if i == 1:
val = ptr.next.data
ptr.next = ptr.next.next
self.length -= 1
return val
return None
Example Testing code:
def testprint(t,message):
print("\n" message,"tree is:",t)
print("Count 'ca', 'can', 'car', 'cat', 'cats':",t.count("ca"),t.count("can"),
t.count("car"),t.count("cat"),t.count("cats"))
print("Size is:",t.size,", max is:",t.max())
t.printAll()
t = StringTree()
t.addAll(["car","can","cat","cat","cat"])
testprint(t,"Initially")
t.add("")
testprint(t,"After adding the empty string")
t.add("ca")
testprint(t,"After adding 'ca'")
t.remove("car")
testprint(t,"After removing 'car'")
t.remove("cat"); t.remove("cat");
testprint(t,"After removing 'cat' twice")
t.remove("ca"); t.add("cats")
testprint(t,"After removing 'ca' and adding 'cats'")
#removing the remaining strings
t.remove("can"); t.remove("cats"); t.remove(“cat”)
print(t, t.size) #None 0
What testing code should be producing:
Initially tree is: (c, 0) -> [None, (a, 0) -> [None, (r, 1) -> [(n, 1) -> [None, None, None], None, (t, 3) -> [None,
None, None]], None], None]
Count 'ca', 'can', 'car', 'cat', 'cats': 0 1 1 3 0
Size is: 5 , max is: cat
car
can
cat
cat
cat
After adding the empty string tree is: (c, 0) -> [None, (a, 0) -> [None, (r, 1) -> [(n, 1) -> [None, None, None], None,
(t, 3) -> [None, None, None]], None], None]
Count 'ca', 'can', 'car', 'cat', 'cats': 0 1 1 3 0
Size is: 5, max is: cat
car
can
cat
cat
cat
After adding 'ca' tree is: (c, 0) -> [None, (a, 1) -> [None, (r, 1) -> [(n, 1) -> [None, None, None], None, (t, 3) ->
[None, None, None]], None], None]
Count 'ca', 'can', 'car', 'cat', 'cats': 1 1 1 3 0
Size is: 6, max is: cat
ca
car
can
cat
cat
cat
After removing 'car' tree is: (c, 0) -> [None, (a, 1) -> [None, (t, 3) -> [(n, 1) -> [None, None, None], None, None],
None], None]
Count 'ca', 'can', 'car', 'cat', 'cats': 1 1 0 3 0
Size is: 5, max is: cat
ca
cat
cat
cat
can
After removing 'cat' twice tree is: (c, 0) -> [None, (a, 1) -> [None, (t, 1) -> [(n, 1) -> [None, None, None], None,
None], None], None]
Count 'ca', 'can', 'car', 'cat', 'cats': 1 1 0 1 0
Size is: 3, max is: cat
ca
cat
can
After removing 'ca' and adding 'cats' tree is: (c, 0) -> [None, (a, 0) -> [None, (t, 1) -> [(n, 1) -> [None, None, None],
(s, 1) -> [None, None, None], None], None], None]
Count 'ca', 'can', 'car', 'cat', 'cats': 0 1 0 1 1
Size is: 3, max is: cats
cat
can
cats
CodePudding user response：
For your remove function you can try to use a similar method to this that has both count and remove, https://ideone.com/3YljlF
while (len(l) > 0):
"""
loop is continue as long as list l contain the elements
"""
# create temporary variable that contain the current node
temp = l[0]
# remove current node from list after creating reference temp
l.remove(l[0])
if (temp.left != None): # if left child is not None append it to list
l.append(temp.left)
if (temp.right != None): # if right child is not None append it to list
l.append(temp.right)
# if both child is None, means it is leaf node increse the count
if (temp.left == None and temp.right == None):
count = 1
return count
CodePudding user response：
This may not be the best answer, but I will be listing to you some of the many problems I see with your code that prevents you from creating suitable functions for this specific BST.
- All your functions will not run because you need to assign left and right sub nodes to your root node.
- The remove function you have written takes as argument what looks like an index rather than a string.
- Both max and count functions have not been tailored for the word tree you are dealing with
- Your max function would be more appropriate perhaps in a case where you do not need specifically the lexicographically largest so you must change this