求助：BST含删除节点的广度优先遍历层级输出实现

你当前代码的核心问题没抓住BFS按层级遍历的关键——得整层整层地处理节点，而不是处理一个节点就把它的子节点单独塞到输出里。你看，现在处理完根节点7，把[5,9]加进输出是对的，但接着处理节点5时直接把[None,6]加进去，处理节点9又把[8,None]加进去，这就把本该是同一层的内容拆成了两个子列表，自然不符合期望的结构。

另外还有两个小坑：

• Node类里没有self.root这个属性，单个节点没法代表整个树的根，遍历逻辑放到Node类里逻辑不通
• 直接打印节点会输出类似<__main__.Node object at 0x...>的内容，得给Node类加个自定义输出的方法，才能得到Node(key)的格式

我调整了代码结构，把树的管理和遍历逻辑放到单独的BST类里，同时严格按照层级批量处理节点的逻辑来实现BFS，完全匹配你要的输出效果：

class Node(object):
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.parent = None
        self.left_child = None
        self.right_child = None

    def __repr__(self):
        # 自定义节点打印格式，满足输出需求
        return f"Node({self.key})"

class BST:
    def __init__(self):
        self.root = None

    def build_from_level_order(self, sequence):
        # 根据你给的层序序列构建二叉搜索树，_代表空节点
        if not sequence:
            return
        self.root = Node(int(sequence[0]))
        queue = [self.root]
        idx = 1
        while queue and idx < len(sequence):
            current = queue.pop(0)
            # 处理左子节点
            if idx < len(sequence) and sequence[idx] != "_":
                current.left_child = Node(int(sequence[idx]))
                queue.append(current.left_child)
            idx += 1
            # 处理右子节点
            if idx < len(sequence) and sequence[idx] != "_":
                current.right_child = Node(int(sequence[idx]))
                queue.append(current.right_child)
            idx += 1

    def breadth_first_traversal(self):
        if not self.root:
            return []
        
        output = []
        current_level = [self.root]
        
        while current_level:
            # 把当前整层的节点加入输出
            output.append(current_level.copy())
            next_level = []
            
            for node in current_level:
                if node is not None:
                    # 实际节点的左右子节点，不存在就加None
                    next_level.append(node.left_child)
                    next_level.append(node.right_child)
                else:
                    # 空节点没有子节点，不用添加
                    pass
            
            # 判断下一层是否全为空，是的话加入输出后停止循环（匹配你的期望输出）
            all_none = all(n is None for n in next_level)
            if all_none:
                if next_level:
                    output.append(next_level)
                break
            current_level = next_level
        
        return output

# 测试用例
if __name__ == "__main__":
    bst = BST()
    # 你的输入序列
    sequence = ["7", "5", "9", "_", "6", "8", "_", "_", "_", "_", "_"]
    bst.build_from_level_order(sequence)
    result = bst.breadth_first_traversal()
    print(result)

1. 拆分Node和BST类：单个Node只负责存储节点属性，BST类管理整个树的根节点、构建和遍历逻辑，避免了原代码中根节点找不到的问题。
2. 层级批量处理：用current_level保存当前层的所有节点，每次循环先把整层加入输出，再批量生成下一层的节点，保证每个子列表对应一个层级。
3. 空节点处理：实际节点的左右子节点不存在时用None填充，空节点则不生成子节点，完美匹配你期望的嵌套列表结构。
4. 停止条件：当下一层全为None时，将其加入输出后停止循环，正好对应你给出的第四层[None, None, None, None]。

运行代码后输出：

[[Node(7)], [Node(5), Node(9)], [None, Node(6), Node(8), None], [None, None, None, None]]

完全符合你的期望。

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