python - 递归构造树而不使用`return`语句?
问题描述
我想询问作为类变量的对象在 Python 中的范围。
import numpy as np
class treeNode:
def __init__(self,key):
self.leftChild = None
self.rightChild = None
self.value = key
def insert(root,key):
if root is None:
return treeNode(key)
else:
if root.value == key:
return root
elif root.value<key:
root.rightChild = insert(root.rightChild,key)
else:
root.leftChild = insert(root.leftChild,key)
return root
def insert_1(root,key):
if root is None:
root = treeNode(key)
else:
if root.value<key:
insert_1(root.rightChild,key)
elif root.value>key:
insert_1(root.leftChild,key)
def construct_tree(a):
def insert_1(root,key):
if root is None:
root = treeNode(key)
else:
if root.value<key:
insert_1(root.rightChild,key)
elif root.value>key:
insert_1(root.leftChild,key)
root = treeNode(a[0])
for k in a:
insert_1(root,k)
return root
if __name__ == '__main__':
np.random.seed(1)
a = np.random.rand(12)
tree = treeNode(a[0])
for k in a:
insert(tree,k)
for k in a:
insert_1(tree,k)
tree_1 = construct_tree(a)
该insert()
函数产生整个树,insert_1()
而construct_tree()
它不返回任何东西,但没有这样做。是否有一个函数可以在不使用return
语句的情况下递归地构造整个树?非常感谢。
解决方案
在insert
中,递归的基本情况是当您插入一个空子树时,通过None
传入 as表示root
。它之所以有效,是因为您可以在这种情况下创建并返回一个新treeNode
的,并且调用者将使用返回值做正确的事情。
如果您不想使用return
,则需要将该基本情况推送到调用代码,这样就可以避免在要添加叶节点时进行调用:
def insert_no_return(root, key):
assert(root != None) # we can't handle empty trees
if root.key == key:
return # no value here, just quit early
elif root.key < key:
if root.rightChild is None: # new base case
root.rightChild = treeNode(key)
else:
insert_no_return(root.rightChild, key) # regular recursive case, with no assignment
elif root.key > key:
if root.leftChild is None: # new base case for the other child
root.leftChild = treeNode(key)
else:
insert_no_return(root.leftChild, key) # no assignment here either
这比带有 的版本更重复return
,因为基本情况需要为每个可能的新孩子重复,但递归行有点短,因为它们不需要在任何地方分配值。
正如断言在顶部所说,您不能在空树(由 表示None
)上有效地调用它,因为它无法更改对None
根的现有引用。所以construct_tree
可能需要特殊的逻辑来构造空树。您当前版本的该函数根本不处理空输入(并且冗余地尝试将根值第二次添加到树中):
def construct_tree(a):
if len(a) == 0: # special case to construct an empty tree
return None
it = iter(a) # use an iterator to avoid redundant insertion of a[0]
root = treeNode(next(it))
for k in it:
insert_no_return(root, k)
推荐阅读
- python - Pymongo:有没有办法在获取数据时在同一个调用中使用查找和聚合
- javascript - 调整输入类型文件上传的图像大小时缺少图像经度和纬度
- apache-kafka - DoctorKafka Metrics Collector (KafkaMetricsCollector) 从 zookeeper 不返回任何代理
- apache-spark - 使用 Spark RDD 保存和加载整个文本文件
- google-chrome - 卡在“将文件同步到设备 Chrome”
- azure-functions - CORS 错误 Azure 函数与 B2C - Blazor
- amazon-web-services - 如何从 EC2 服务创建/访问不同 AWS 账户中的多个 Dynamo DB 表?
- laravel - 简单的 Laravel 项目抛出未定义的变量错误
- javascript - 事件循环和承诺
- kotlin - TornadoFX _ Kotlin _ IntelliJ IDEA:由于我在项目中使用 openJDK 8,我怎么可能得到“未解决的参考:javafx”?