我創建了兩個類，STNode 和 StringTree。在我的 StringTree 類中，最后三個函式（count、max 和 remove）出現問題。我添加了注釋以顯示我希望我的代碼執行當前不是的操作。理想情況下，我只想對我的 StringTree 類進行更改，因為我對 STNode 非常滿意。
進一步解釋我的代碼的目的：每個節點都有三個孩子：左、右和前；
- 每個節點包含一個字符（節點的資料）和一個非負整數（存盤資料的多重性）。
- 節點的左子節點（如果存在）包含一個小于（按字母順序）節點字符的字符
- 節點的右子節點（如果存在）包含大于節點字符的字符
代碼：
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
示例測驗代碼：
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
應該生成什么測驗代碼：
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
uj5u.com熱心網友回復：
對于您的洗掉功能，您可以嘗試使用與此類似的方法，該方法同時具有計數和洗掉功能，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
uj5u.com熱心網友回復：
這可能不是最好的答案，但我將向您列出我在您的代碼中看到的許多問題中的一些，這些問題阻止您為這個特定的 BST 創建合適的函式。
- 您的所有功能都不會運行，因為您需要將左右子節點分配給根節點。
- 您撰寫的 remove 函式將看起來像索引而不是字串的引數作為引數。
- max 和 count 函式都沒有為你正在處理的詞樹量身定做
- 您的 max 函式可能更適合在您不需要特別按字典順序排列的最大的情況下，因此您必須更改它
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/362732.html
標籤：Python string max binary-tree binary-search-tree
上一篇：如何在Rust中加入字符向量