递归构建二叉决策树时遇到问题 python

Question

我正在尝试递归构建二元决策树，用于诊断 python 3 中的疾病。生成器获取记录列表（每个记录都是一种疾病及其症状列表）和症状列表，如下所示：

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']

并构建一个二叉树，每个级别检查症状是真还是假，每个级别都有一个 child 节点。右边的 child 总是表示符号不存在，左边的表示符号存在。对于示例数据，树应该如下所示：

                       1
               2                    2
          3        3          3            3
    None   B     A   None   C  None   None     Healthy

例如，叶子A是通过询问： 1：真 2：错误 3：真它的路径是 [1,3]（真值）

这是我正在使用但无法正常工作的代码：

def builder(records, symptoms, path):
    #Chekl if we are in a leaf node that matches an illness
    for record in records:
        if path == record.symptoms:
            return Node(record.illness,None,None)

     #No more symptoms means an empty leaf node
    if len(symptoms) == 0:
        return Node(None,None,None)

    #create subtree
    else:
        symptom = symptoms.pop(0)
        right_child = builder(records,symptoms,path)
        path.append(symptom)
        left_child = builder(records,symptoms,path)
        return  Node(symptom,right_child,left_child)

我试过感冒运行，在纸上效果很好。我不确定我遗漏了什么，但是生成的树有很多空节点，而不是有病的节点。也许我弄乱了路径，但我现在不确定如何修复它。

Answer 1

您的 symptoms.pop(0) 正在影响一个 symptoms 列表，该列表由对 builder 的所有调用共享。这在下降过程中很好，因为您只想考虑后续症状。但是当递归调用 returns 时，您的列表缺少元素。（如果它 returns 没有找到匹配项，它就是空的！）同样，共享的 path 会永远增长。

简单但效率低下的答案是在递归时创建新列表：

symptom=symptoms[0]
symptoms=symptoms[1:]
path=path+[symptom]  # not +=

递归构建二叉决策树时遇到问题 python

Trouble recursively building a binary decision tree python

python

algorithm

tree

recursion

binary-tree