如圖,我現在想要實現改變二元搜尋樹的每個節點成為"自己與所有比自己小的節點值"的總和
終端機輸出必須是這個:
Before : 4 2 6 1 3 5 7
After: 10 3 21 1 6 15 28
這是我寫的程式:
class Node:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, new):
if self.root == None: # 若樹根為空
self.root = Node(new)
else:
cur = self.root
while cur: # 迴圈會在走到 None 的時候結束
parent = cur # 把父節點的位置保存下來
if cur.val > new: # 若當前節點比插入值大,則往左子樹走
cur = cur.left
elif cur.val < new: # 若當前節點比插入值小,則往右子樹走
cur = cur.right
else: # 若當前節點等於插入值,則直接離開insert()
return
if parent.val > new: # 若父節點比插入值大,則插入父節的點的左子樹
parent.left = Node(new)
else: # 若父節點比插入值小,則插入父節的點的右子樹
parent.right = Node(new)
def levelorder(self):
queue = [self.root]
while queue!=[]:
print(queue[0].val, end = " ")
if queue[0].left:
queue.append(queue[0].left)
if queue[0].right:
queue.append(queue[0].right)
queue.pop(0)
print()
# ======================================== 題目 ========================================
def sum_of_smaller(self, now):
#用遞迴方式完成中序走訪
if now is None: return #如果現在的節點是空的,直接回傳
self.sum_of_smaller(now.left) #走訪左節點
print(now.val) #印出走訪到的節點
self.sum_of_smaller(now.right)#走訪右節點
# ======================================================================================
if __name__ == "__main__":
# 建立二元搜尋樹物件,並且加入節點
bst = BST()
lst = [4, 2, 6, 1, 3, 5, 7]
for val in lst:
bst.insert(val)
# 顯示原始二元樹的階層走訪
print("Before : ", end = "")
bst.levelorder()
# 使用 sum_of_smaller 方法來改變 bst 物件本身
bst.sum_of_smaller(bst.root)
# 顯示更改後二元樹的階層走訪
print("After : ", end = "")
bst.levelorder()
我目前是用遞迴的方式寫出中序走訪(sum_of_smaller
函式),發現這個樹走訪完剛好就是1,2,3,4,5,6,7,我只要把一個節點和它前面的節點們加總起來就會有答案。
但是我嘗試一些方法....... 都不是我要的。像是額外設一個total = 0
變數,再做 total += now.val
但結果都是0。另外,這程式的結果應該要直接改變二元樹本身。
請問這部分要怎麼解? 解答要放在sum_of_smaller
函式中
我只想得到兩種寫法
以下是一種
1.修改 levelorder,將所有節點值建立一個 list=[1,2,3,4,5,6,7]
2.複製 levelorder 成為 sum_of_smaller,並修改以下兩個部份
2.1 不需要將節點值建立 list
2.2 用「節點值和 list」計算出「新的節點值」並取代原節點值
2.3 print 出新的節點值
我不能修改levelorder,題目有要求我只能動sum_of_smaller那一區。所以我才希望能直接在sum_of_smaller的遞迴裡完成加總。
那得再想想了
加一列now.val = sum(filter(lambda x: x<=now.val, lst))
# ======================================== 題目 ========================================
def sum_of_smaller(self, now):
#用遞迴方式完成中序走訪
if now is None: return #如果現在的節點是空的,直接回傳
self.sum_of_smaller(now.left) #走訪左節點
now.val = sum(filter(lambda x: x<=now.val, lst))
print(now.val) #印出走訪到的節點
self.sum_of_smaller(now.right)#走訪右節點
# ======================================================================================