如何計算數字符合謂詞的數字樹？

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