Как сохранить значение во всей рекурсивной функции (проблема kdtree) - PullRequest
Новая
       27

Как сохранить значение во всей рекурсивной функции (проблема kdtree)

1 голос
/ 28 мая 2019

Я программирую Kdtrees на Python 3, и у меня возникла проблема с функцией, предназначенной для определения, находится ли узел, введенный в аргументах, в Kdtree.

Я использую рекурсивную функцию, но она возвращает None дажекогда точка присутствует. 


#I put the init to show you how the kdnode is made

class KdNode:

def __init__(self, point, dim, left_child, right_child):
   self.point = point;
   self.dim = dim;
   self.left_child = left_child;
   self.right_child = right_child;


def KdTree_present(kdnode,point_to_test):
    if kdnode == None:
        return
    else:

        KdTree_present(kdnode.left_child, point_to_test)
        KdTree_present(kdnode.right_child, point_to_test)
        if kdnode.point == point_to_test:

            return True


#Kdnode_example = [(150, 300), 1, [(200, 250), 0, None, None], [(325, 400), 0, None, None]]

Даже вывод KdTree_present должен быть True, это всегда None.

1 Ответ

1 голос
/ 29 мая 2019

К какому типу относится точка?Помните, что если вы сравниваете объекты, вы всегда получите false, если они не находятся в одном и том же пространстве памяти (они указывают на один и тот же объект), обратитесь к этому вопросу Сравните экземпляры объектов на равенство по их атрибутам в Python

Для работы == вам необходимо переопределить функцию __eq__ в точке.Либо создайте эту функцию, либо измените ваше состояние на что-то вроде if knode.point.x == point_to_test.x and knode.point.y == point_to_test.y

Редактировать:

Чтобы добавить к вашему комментарию, действительно есть проблема с рекурсией, она будет проходить через все дочерние элементы доон возвращает False, так как дочерних элементов больше нет, или возвращает True, если он находит его, что бы ни было быстрее, вам следует сделать следующее: 

def KdTree_present(kdnode,point_to_test):
    if kdnode == None:
        return False
    if kdnode.point == point_to_test:
        return True 
    return KdTree_present(kdnode.left_child, point_to_test) or KdTree_present(kdnode.right_child, point_to_test)
...