Блог

Я хотел бы узнать о области видимости в 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 передачей как 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)