递归地构造树而不使用“return”语句？

Question

我想询问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语句？多谢各位

Answer 1

在insert中，递归的基本情况是插入到空子树中，表示为None作为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)