遞回列印樹的節點時出錯

示意圖：有一個節點類來支持樹結構。此類的每個實體都將有一個用于其所有子級、父級和要存盤的資料的字典。

make_children 接受呼叫物件并將引數添加為子物件。由于當前呼叫物件是父節點，因此子節點的父節點設定為 self。然后將此子項作為子項添加到當前物件字典中。

print_tree 獲取當前呼叫物件并列印 value 屬性，同時遞回呼叫自身并在遇到葉節點時停止。

我試圖玩弄和學習遞回和樹。我正在嘗試獲得以下輸出。

[12, 7, 8, 15]
[12, 7]
[8, 15]
[12]
[7]
[8]
[15]

而是得到：

[12, 7, 8, 15]
[12, 7]
[8, 15]

我在做什么錯？我懷疑問題出在 print_tree、build_file_tree 中的 recusion 或 build_file_tree 中的 return 陳述句上。我嘗試使用列印陳述句列印左半部分和右半部分，它們似乎作業正常，這讓我更傾向于 print_tree。

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []
        self.parent = None

    def make_children(self, child):
        child.parent = self
        self.children.append(child)

    def print_tree(self): #ISSUE?
        print(self.value)
        if len(self.children) > 0: # leaf node case
            for child in self.children:
                child.print_tree()

    
def build_file_tree(list1):
    
    #list1 = [12, 7, 8, 15]
    #root = Node(56)
    root = Node(list1)
    #child1 = Node(12)
    #child2 = Node(24)

    temp = len(list1) // 2
    left_half = list1[:temp]
    right_half = list1[temp:]

    if len(left_half) > 1:  # ISSUE HERE?
        build_file_tree(left_half)

    if len(right_half) > 1: # ISSUE HERE?
        build_file_tree(right_half)

    child1 = Node(left_half)
    child2 = Node(right_half)

    root.make_children(child1)
    root.make_children(child2)

    return root #ISSUE?


if __name__ == '__main__':
    list1 = [12, 7, 8, 15]
    file = build_file_tree(list1)
    file.print_tree()

uj5u.com熱心網友回復：

除錯步驟：

def __init__(self, value):
   print(f"Creating node for {value}")

這將向您展示您實際上創建了兩個不同的樹。這是由于在 as 上呼叫（Node應該呼叫Tree），然后在left_halfas中呼叫。Node(left_half)build_file_tree(left_half)Node(list1)

這意味著每個子樹的高度只有 2 級，之后您將呼叫 make_children 并使用未設定其父關系集的新實體。

build_file_tree我的解決方案是按如下方式更改功能：

def build_tree(value_list):
    root = Tree(value_list)
    if len(value_list) == 1:
        return root
        
    mid_point = len(value_list) // 2
    left_half = value_list[:mid_point]
    right_half = value_list[mid_point:]

    child1 = build_tree(left_half)
    root.make_child(child1)

    child2 = build_tree(right_half)
    root.make_child(child2)

    return root

我做了一些簡單的重構，但你應該能夠理解

uj5u.com熱心網友回復：

如果串列的長度為 1，則不會創建 Child。但是，如果您想要描述的行為，則應該這樣做。list1如果只包含一個或更少的元素，您還需要停止遞回。而且你沒有抓住回傳的root元素。您的代碼可能如下所示：

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []
        self.parent = None

    def make_children(self, child):
        child.parent = self
        self.children.append(child)

    def print_tree(self): #ISSUE?
        print(self.value)
        if len(self.children) > 0: # leaf node case
            for child in self.children:
                child.print_tree()

    
def build_file_tree(list1):
    
    #list1 = [12, 7, 8, 15]
    #root = Node(56)
    root = Node(list1)
    #child1 = Node(12)
    #child2 = Node(24)
    if len(list1) > 1:
        temp = len(list1) // 2
        left_half = list1[:temp]
        right_half = list1[temp:]

        child1 = build_file_tree(left_half)
        root.make_children(child1)

        child2 = build_file_tree(right_half)
        root.make_children(child2)

    return root


if __name__ == '__main__':
    list1 = [12, 7, 8, 15]
    file = build_file_tree(list1)
    file.print_tree()

標籤：Python 递归 树

上一篇：無論深度如何，如何通過減去屬性來獲得兩個物件的差異？

下一篇：解決此遞回的最佳方法是什么？