如何计算数字符合谓词的数字树？

Question

我想定义一个计数函数来计算树中满足谓词的每个数字。

#given function: 
class TN: 
    def __init__(self,value,left=None,right=None): 
     self.value = value 
     self.left = left 
     self.right = right 

def add(atree,value): 
    if atree == None: 
     return TN(value) 
    if value < atree.value: 
     atree.left = add(atree.left,value) 
     return atree 
    elif value > atree.value: 
     atree.right = add(atree.right,value) 
     return atree 
    else: 
     return atree # already in tree 

def add_all(atree,values): 
    for v in values: 
     atree = add(atree,v) 
    return atree 

def is_prime (x): 
    assert type(x) is int and x >= 0, 'predicate.is_prime x is not a positive int: '+str(x) 
    if x <= 2: 
     return x == 2 
    for i in range(2,x): 
     if x % i == 0: 
      return False 
    return True 

add_all函数接受一个列表并返回一棵树。 如果int参数为素数，则is_prime函数返回True。

#function I am trying to define (a recursive function: count): 
def count(t,p): 
    if t==None: 
     return 0 
    else: 
     return 1+count((t.left if p(t.left.value) else t.right),p) 

例如，

import random 
values = [i for i in range(1,200)] 
random.shuffle(values 

） ###调用计数功能如下应该给我： 计数（add_all（无，值），is_prime）＃ - > 46

我计数功能给我：

AttributeError: 'NoneType' object has no attribute 'value' 

我是新来使用TR ee，我认为我有问题来定义递归计数函数。

Answer 1

您的至少一个t.left属性是None。根据理由，二叉树不会永远持续下去。

但是，如果要计算与谓词匹配的所有值，则必须遍历所有这些元素，而不仅仅是与谓词匹配的元素。始终遍历节点，但只返回匹配节点的计数：

def count(t, p): 
    if t is None: 
     return 0 
    result = 1 if p(t.value) else 0 
    return count(t.left, p) + result + count(t.right, p) 

E.g.返回当前节点的计数（0或1）加上左右节点的递归计数。如果其中任何一个为None，则递归函数将停止并为那些返回0。

你甚至可以只使用：

def count(t, p): 
    if t is None: 
     return 0 
    return count(t.left, p) + p(t.value) + count(t.right, p) 

因为在Python中，布尔类型是int其中True == 1和False == 0一个子类;求和整数和布尔值将布尔值视为整数：

>>> 0 + True 
1