class tree():
def __init__(self):
'''Initialise the tree'''
self.Data = None
self.Count = 0
self.LeftSubtree = None
self.RightSubtree = None
def Insert(self, data):
'''Add an item of data to the tree'''
if self.Data == None:
self.Data = data
self.Count += 1
elif data < self.Data:
if self.LeftSubtree == None:
# tree is a recurive class definition
self.LeftSubtree = tree()
# Insert is a recursive function
self.LeftSubtree.Insert(data)
elif data == self.Data:
self.Count += 1
elif data > self.Data:
if self.RightSubtree == None:
self.RightSubtree = tree()
self.RightSubtree.Insert(data)
if __name__ == '__main__':
T = tree()
# The root node
T.Insert('b')
# Will be put into the left subtree
T.Insert('a')
# Will be put into the right subtree
T.Insert('c')
我想知道你是不是说“递归”。下面是计算factorial function的递归函数的一个简单示例:
递归算法的两个关键元素是:
n == 0
factorial(n - 1)
Python中的递归与其他语言中的递归一样工作,递归构造是根据自身定义的:
例如,递归类可以是二叉树(或任何树):
如前所述,递归结构必须具有终止条件。在这个类中,它不那么明显,因为它只在添加新元素时递归,并且只额外执行一次。
同样值得注意的是,python在默认情况下对可用的递归深度有一个限制,以避免吸收计算机的所有内存。在我的电脑上是1000。我不知道这是否取决于硬件等的变化来查看您的:
设置它:
编辑:我不能保证我的二叉树是有史以来最有效的设计。如果有人能改进,我很高兴听到
假设您想要构建: u(n+1)=f(u(n)),其中u(0)=u0
一种解决方案是定义一个简单的递归函数:
不幸的是,如果要计算u的高值,将遇到堆栈溢出错误。
另一个解决方案是一个简单的循环:
但是如果你想要多个u值来表示不同的n值,这是次优的。可以缓存数组中的所有值,但可能会遇到内存不足错误。您可能希望改用生成器:
还有很多其他的选择,但我想这些是主要的。
相关问题 更多 >
编程相关推荐