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

Я программирую 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.

python recursion kdtree

28.05.2019 22:35

Почему в Python есть оператор "pass"?

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Некоторые методы, о которых вы не знали, что они существуют в Python

Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...

Основы Python Часть I

Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?

LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

Оптимизация кода с помощью тернарного оператора Python

И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это

Советы по эффективной веб-разработке с помощью Python

Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.

Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Какой тип точки? Помните, что если вы сравниваете объекты, вы всегда получите 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)

Спасибо за ответ. Point — это массив [x,y]. У меня сложилось впечатление, что == работает хорошо из-за типа «точка». Я думаю, что проблема в рекурсии

— 29.05.2019 09:23

28.05.2019 23:44