iT邦幫忙

0

二元搜尋樹的節點加總問題

  • 分享至 

  • xImage

如圖,我現在想要實現改變二元搜尋樹的每個節點成為"自己與所有比自己小的節點值"的總和
https://ithelp.ithome.com.tw/upload/images/20220513/201489299wtja0xbBr.png
終端機輸出必須是這個:

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函式中

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 個回答

0
海綿寶寶
iT邦大神 1 級 ‧ 2022-05-14 10:11:07

我只想得到兩種寫法
以下是一種
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的遞迴裡完成加總。

https://ithelp.ithome.com.tw/upload/images/20220514/20001787b6sdBaZtdI.png
那得再想想了

加一列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)#走訪右節點
        
# ======================================================================================

我要發表回答

立即登入回答