Python 3递归构建疾病诊断二叉决策树遇问题求助

你的代码核心问题出在可变对象（列表）在递归过程中被共享修改，导致path和symptoms的状态混乱，最终无法匹配到对应的疾病记录。咱们一步步拆解问题：

1. 症状列表symptoms的错误处理 #

你用了symptoms.pop(0)来获取当前症状，这会直接修改原列表。递归调用时，左右子树拿到的symptoms是同一个被修改后的列表，这会导致后续分支的症状顺序完全混乱。比如第一次递归弹出'1'后，原symptoms变成['2','3']，右子树递归时用的就是这个修改后的列表，而不是原始的剩余症状集合。

2. 路径path的错误处理 #

path是可变列表，你在递归中直接path.append(symptom)，这会让所有递归分支共享同一个path实例。比如先处理右子树（症状不存在，path不变），然后修改path去处理左子树，但右子树递归过程中已经使用了这个path，后续的修改会影响之前的匹配判断，导致永远无法和record.symptoms完全一致。

修复后的代码 #

class Node:
    def __init__(self, data="", pos=None, neg=None):
        self.data = data
        self.positive_child = pos
        self.negative_child = neg

class Record:
    def __init__(self, illness, symptoms):
        self.illness = illness
        self.symptoms = symptoms

records = [Record('A',['1','3']), Record('B',['1','2']), Record('C',['2','3'])]
symptoms = ['1','2','3']

def builder(records, symptoms, path):
    # 如果剩余记录都属于同一种疾病，直接返回疾病叶子节点
    unique_illnesses = set(r.illness for r in records)
    if len(unique_illnesses) == 1:
        return Node(unique_illnesses.pop(), None, None)
    
    # 没有症状可询问时，返回空叶子节点
    if not symptoms:
        return Node(None, None, None)
    
    # 取当前要询问的症状，用切片传递剩余症状（不修改原列表）
    current_symptom = symptoms[0]
    remaining_symptoms = symptoms[1:]
    
    # 拆分记录：包含当前症状的（左子树分支）和不包含的（右子树分支）
    records_with_symptom = [r for r in records if current_symptom in r.symptoms]
    records_without_symptom = [r for r in records if current_symptom not in r.symptoms]
    
    # 递归构建左右子树，传递path的副本（避免分支间互相干扰）
    left_child = builder(records_with_symptom, remaining_symptoms, path + [current_symptom])
    right_child = builder(records_without_symptom, remaining_symptoms, path)
    
    return Node(current_symptom, left_child, right_child)

# 测试调用
root = builder(records, symptoms, [])

关键修改点说明 #

1. 不修改原symptoms列表：用symptoms[0]获取当前症状，symptoms[1:]传递剩余症状的新列表，确保每个递归分支拿到的都是独立的症状集合。
2. 传递path的副本：用path + [current_symptom]创建新的路径列表，避免不同递归分支的路径状态互相干扰。
3. 优化匹配逻辑：原逻辑只有当path完全等于record.symptoms时才返回疾病节点，现在改为当剩余记录都属于同一种疾病时就返回该节点，更符合决策树的实际逻辑，也避免了不必要的空节点。

用你的示例数据测试，现在可以正确生成预期的树结构：

• 根节点是'1'，左子节点（症状存在）处理症状'2'，右子节点（症状不存在）处理症状'2'。
• 根节点左子节点的左子节点（症状2存在）是疾病B，右子节点（症状2不存在）处理症状'3'，其左子节点是疾病A。
• 根节点右子节点的左子节点（症状2存在）处理症状'3'，其左子节点是疾病C。

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