使用unittest测试红黑树时如何忽略嵌套结构的parent字段？

问题根源 #

你猜的没错，dataclass默认的__eq__方法会递归对比所有属性，而Node的parent属性形成了循环引用（父节点指向子节点，子节点又指向父节点），导致self.assertEqual(tree, expected_tree)执行时无限递归，最终触发RecursionError。

解决办法 #

方法1：自定义Node的__eq__方法，忽略parent属性 #

直接修改Node类，重写__eq__方法，只对比color、value、left、right这些核心属性，跳过parent：

@dataclass
class Node(Generic[T]):
    color: Color
    value: T
    parent: Optional['Node[T]'] = None
    left: Optional['Node[T]'] = None
    right: Optional['Node[T]'] = None

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Node):
            return False
        # 只比较关键属性，不处理parent
        return (self.color == other.color
                and self.value == other.value
                and self.left == other.left
                and self.right == other.right)

这样dataclass生成的默认__eq__会被覆盖，对比时不会递归处理parent，自然避免循环引用问题。

方法2：测试时手动遍历验证结构，不直接对比整个树 #

如果不想修改Node类的默认行为，可以在测试里写一个遍历函数，逐个验证节点的核心属性，替代self.assertEqual(tree, expected_tree)：

def _compare_nodes(self, actual: Optional[Node], expected: Optional[Node]):
    if actual is None and expected is None:
        return
    self.assertIsNotNone(actual)
    self.assertIsNotNone(expected)
    self.assertEqual(actual.color, expected.color)
    self.assertEqual(actual.value, expected.value)
    # 递归对比左右子节点，不涉及parent
    self._compare_nodes(actual.left, expected.left)
    self._compare_nodes(actual.right, expected.right)

def test_left_rotation(self):
    # ... 原有测试代码 ...

    # 替换原来的self.assertEqual(tree, expected_tree)
    self._compare_nodes(tree.root, expected_tree.root)

这种方式完全由你控制验证内容，既能避开循环引用，也能精准检查树的结构。

方法3：给dataclass加eq=False，自定义树的对比逻辑 #

给Node和RedBlackTree添加eq=False参数，然后手动实现树的__eq__方法：

@dataclass(eq=False)
class Node(Generic[T]):
    color: Color
    value: T
    parent: Optional['Node[T]'] = None
    left: Optional['Node[T]'] = None
    right: Optional['Node[T]'] = None

@dataclass(eq=False)
class RedBlackTree(Generic[T]):
    root: Node

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, RedBlackTree):
            return False
        # 自定义节点对比逻辑，跳过parent
        def compare_nodes(a: Optional[Node], b: Optional[Node]) -> bool:
            if a is None and b is None:
                return True
            if a is None or b is None:
                return False
            return (a.color == b.color
                    and a.value == b.value
                    and compare_nodes(a.left, b.left)
                    and compare_nodes(a.right, b.right))
        return compare_nodes(self.root, other.root)

这样树的对比会按你写的逻辑执行，不会触发循环递归。

额外建议 #

测试红黑树时，可以单独验证parent属性的正确性：比如遍历每个节点，检查子节点的parent是否指向正确的父节点。这样既避开了循环对比，又能确保父子关系无误。

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