递归打印树的节点时出错

Question

示意图：有一个节点 class 用于支持树结构。这个 class 的每个实例都将有一个字典，用于它们的所有子项、一个父项和要存储的数据。

make_children 获取调用对象并将参数添加为子对象。 childs parent 设置为 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 中的回避或 build_file_tree 中的 return 语句。我尝试使用 print 语句打印左半边和右半边，它们似乎工作正常，这让我更倾向于 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()

Answer 1

如果列表的长度为 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()

Answer 2

调试步骤：

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

这将向您展示您实际上创建了两棵不同的树。这是由于在 left_half 上调用 Node（应称为 Tree）为 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

我做了一些轻微的重构，但你应该能理解这个想法

递归打印树的节点时出错

Error in recursively printing nodes of a tree

python

recursion

tree