如何在整个递归函数中保持一个值（kdtree 问题）

Question

我使用 Python 3 对 Kdtrees 进行编程，但我遇到了一个问题，该函数旨在确定参数中的节点是否在 Kdtree 中。

我使用递归函数，但它 returns 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。

Answer 1

点是什么类型？请记住，如果您比较对象，除非它们在相同的 space 内存中（它们指向相同的对象），否则您将始终得到 false，请参阅此问题 Compare object instances for equality by their attributes in Python

要使 == 工作，您必须重写函数 __eq__ in point。创建该函数或将您的条件更改为 if knode.point.x == point_to_test.x and knode.point.y == point_to_test.y

编辑：

添加到您的评论中，递归确实存在问题，它将遍历所有子项直到它 returns False 因为没有更多的子项，或者 return 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)

如何在整个递归函数中保持一个值（kdtree 问题）

How to keep a value throughout a recursive function (kdtree problem)

python

recursion

kdtree