决策树中的递归编程

Question

我正在用python编写决策树。 tree是具有真分支tb和假分支fb的对象。只有根节点具有属性results。

results是包含节点处的每个目标变量（即因变量）的计数的字典。我正在处理一个二进制分类问题，所以一个例子将是一本字典{0: 25, 1: 9}。

我想创建一个函数findrootnodes(tree)，它遍历树遍历到根节点。它应该返回列表根节点。列表中的每个元素都应该包含一个字典。因此，具有四个根节点的决策树的示例将是[{0: 25, 1: 9}, {0: 2, 1: 65}, {0: 2, 1: 7}, {0: 52, 1: 4}]。

我该怎么做？我目前的代码在下面，但问题是它总是返回一个空列表。如果我将根节点带出函数，Python会抱怨局部变量rootnode在实例化之前被引用。

def findrootnodes(tree): 
    rootnodes = [] 
    if tree.results != None: 
     rootnodes += tree.results 
    else: 
     findrootnodes(tree.tb) 
     findrootnodes(tree.fb) 
    return rootnodes 

Answer 1

在你findrootnodes功能，你永远不会改变的rootnodes非结果节点的值。也就是说，当你调用findrootnodes，你先设置：

rootnodes = [] 

假设初始节点没有results，然后运行：

findrootnodes(tree.tb) 
    findrootnodes(tree.fb) 

...均未改变的rootnodes值。然后你返回rootnodes，这仍然是一个空的列表。

我认为你真正想要的是：

def findrootnodes(tree): 
    rootnodes = [] 
    if tree.results != None: 
     rootnodes.append(tree.results) 
    else: 
     rootnodes.extend(findrootnodes(tree.tb)) 
     rootnodes.extend(findrootnodes(tree.fb)) 
    return rootnodes 

请注意，我已经改变了你的+=这里.append(...)，因为这样：

>>> x = [] 
>>> x += {'key': 'value'} 
>>> x 
['key'] 

如果添加字典到通过+=列表将视字典为迭代，Python将遍历只是键。