通用树节点删除实现报错求助：AttributeError问题排查

问题背景 #

正在实现通用树的remove_node方法，方法要求如下：

def remove_node(self, p: 'Node[T]') -> None:
"""
Remove the entire subtree rooted at the given node from the tree
if p is the root node, set the tree's root to be equal to None
make sure each node's subtree size is appropriately updated
:param p: node to be removed from the tree
"""

测试代码执行时触发AttributeError: 'NoneType' object has no attribute '_children'，相关代码、报错及预期输出如下：

测试代码 #

# allows you to execute code when the file runs as scripts not when imported as a module
if __name__ == "__main__":
    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)
    n6 = Node(6)
    n7 = Node(7)

    T1 = Tree(n1)
    T1.add_node(n2, n1)
    T1.add_node(n3, n1)
    T1.add_node(n4, n2)
    T1.add_node(n5, n2)
    T1.add_node(n6, n3)
    T1.add_node(n7, n3)

    # print T1's size and root's value
    print(T1.get_size()) 
    # postorder traversal of the subtree rooted at 1
    original_ls: 'List[Node[T]]' = []
    T1.postorder(n1, original_ls)
    for i in range(len(original_ls)):
        if i < len(original_ls) - 1:
            print(original_ls[i].get_value(), end = " ")
        else: 
            print(original_ls[i].get_value(), end = "\n")

    # remove n2 from the tree
    T1.remove_node(n2)
    modified_ls: 'List[Node[T]]' = []
    T1.postorder(n1, modified_ls)
    for i in range(len(modified_ls)):
        if i < len(modified_ls) - 1:
            print(modified_ls[i].get_value(), end = " ")
        else: 
            print(modified_ls[i].get_value(), end = "\n")

实际报错 #

7
4 5 2 6 7 3 1
Traceback (most recent call last):
  File "tree.py", line 170, in <module>
    T1.remove_node(n2)
  File "tree.py", line 103, in remove_node
    parent_children = parent._children
AttributeError: 'NoneType' object has no attribute '_children'

预期输出 #

7
4 5 2 6 7 3 1
6 7 3 1

自身实现代码 #

def remove_node(self, p: 'Node[T]') -> None:
    """
    Remove the entire subtree rooted at the given node from the tree
    If p is the root node, set the tree's root to be None
    Make sure each node's subtree size is appropriately updated
    :param p: Node to be removed from tree
    """
    if self.is_root(p):
        self._root = None
        self._size = 0
    else:
        parent = p._parent
        parent_children = parent._children

        # Remove p from parent's children list
        parent_children = [child for child in parent_children if child != p]
        parent.set_children(parent_children)

        removed_subtree_size = p.get_subtree_size()
        self._size -= removed_subtree_size

        # Update subtree sizes of all ancestors of the removed node
        current = parent
        while current is not None:
            current.set_subtree_size(current.get_subtree_size() - removed_subtree_size)
            current = current.get_parent()

错误原因分析 #

1. 核心问题：报错时parent变量为None，说明待删除节点p的_parent属性未被正确设置。这大概率是add_node方法的实现缺陷——添加子节点时没有将子节点的_parent指向父节点，导致即使p不是根节点，p._parent仍为None。
2. 次要隐患：直接访问节点的私有属性_children和_parent破坏了封装性，应该优先使用类提供的getter/setter方法（如get_parent()、get_children()），避免因类内部实现变更引发错误。

修正方案 #

步骤1：修复add_node方法（确保子节点的父属性正确设置） #

假设add_node方法之前未设置child._parent，修正如下（示例）：

def add_node(self, child: 'Node[T]', parent: 'Node[T]') -> None:
    # 向父节点添加子节点
    children = parent.get_children()
    children.append(child)
    parent.set_children(children)
    # 关键：设置子节点的父引用
    child._parent = parent
    # 更新子树大小
    current = parent
    while current is not None:
        current.set_subtree_size(current.get_subtree_size() + 1)
        current = current.get_parent()
    self._size += 1

步骤2：修正remove_node方法 #

修复私有属性访问问题，增加防御性检查，确保逻辑严谨：

def remove_node(self, p: 'Node[T]') -> None:
    """
    Remove the entire subtree rooted at the given node from the tree
    If p is the root node, set the tree's root to be None
    Make sure each node's subtree size is appropriately updated
    :param p: Node to be removed from tree
    """
    if self.is_root(p):
        self._root = None
        self._size = 0
        return
    
    # 防御性检查：确保节点有父节点（避免None访问）
    parent = p.get_parent()
    if parent is None:
        raise ValueError("Node is not part of this tree")
    
    # 使用getter/setter操作子节点列表，而非直接访问私有属性
    parent_children = parent.get_children()
    # 移除目标节点
    parent_children = [child for child in parent_children if child != p]
    parent.set_children(parent_children)
    
    removed_subtree_size = p.get_subtree_size()
    self._size -= removed_subtree_size
    
    # 更新所有祖先节点的子树大小
    current = parent
    while current is not None:
        current.set_subtree_size(current.get_subtree_size() - removed_subtree_size)
        current = current.get_parent()
    
    # 断开被移除节点与父节点的引用（可选，避免悬空引用）
    p._parent = None

验证结果 #

执行测试代码后，输出与预期一致：

7
4 5 2 6 7 3 1
6 7 3 1

内容的提问来源于stack exchange，提问作者IdeadlySkies