python - 与 Python 中的递归和属性 setter 混淆

Question

我正在尝试实现二叉搜索树类。我有两个类(class)； BSTNode 和 BST。我尝试在 left 和 right 的 setter 中强制执行搜索树属性:

class BSTNode(object):


    def __init__(self,new):
        if type(new) is BSTNode:
            self._data = new.data
        else:
            self._data = new
        self._left = None
        self._right = None


    @property
    def data(self):
         return self._data


    @property
    def left(self):
        return self._left


   @left.setter
   def left(self,data):
        if data is None:
            self._left = None
        else:
            n = BSTNode(data)
            if n.data >= self.data:
                del n
                raise ValueError("Value must be less-than parent!")
            self._left = n


    @property
    def right(self):
        return self._right


    @right.setter
    def right(self,data):
        if data is None:
            self._right = None
        else:
            n = BSTNode(data)
            if n.data < self.data:
                del n
                raise ValueError("Value must be greater-than or equal-to parent!")
            self._right = n


class BST(object):


    def __init__(self):
        self._root = None


    @property
    def root(self):
        return self._root


    @root.setter
    def root(self,value):
        self._root = BSTNode(value)


    def binary_insert(self,list_in):
        self.root = binary_insert(list_in,0,len(list_in) - 1)

现在，我正在尝试实现一个方法 binary_insert(self,list_in)，我将一个排序列表插入到树中，使树是平衡的(本质上使用二分查找)；然而，我在 root 的左右节点始终是 None，尽管我在函数中明确地分配了它们，而且我确信我的索引是正确的，因为我得到了运行时打印如下:

> t = BST()
> list_in = [0,1,2,3,4,5,6,7,8]
> t.binary_insert(list_in)
4
1
0
2
3
6
5
7
8

这是我的函数(注意上面 BST 类中的实例方法 binary_insert):

def binary_insert(list_in,imin,imax):
    if imax < imin:
        return None
    imid = int(floor((imax + imin) / 2))
    n = BSTNode(list_in[imid])
    print(n.data)
    n.left = binary_insert(list_in,imin,imid-1)
    n.right = binary_insert(list_in,imid+1,imax)
    return n

我总是返回一个 BSTNode，只有当 setter 的输入是 None 时，它才为 None，尽管函数运行后的树是root。我怀疑我不了解的属性正在发生某些事情。我想对此做一些澄清。

 > t = BST()
 > list_in = [0,5,12]
 > t.binary_insert(list_in)
 5
 0
 12
 > t.root.data 
 5
 > t.root.left
 None
 > t.root.right
 None

预期:

 > t.root.left.data
 0
 > t.root.right.data
 12

Answer 1

出现此问题是因为在完成所有递归并将根创建为 BSTNode 之后执行以下行 -

self.root = binary_insert(list_in,0,len(list_in) - 1)

也就是最后binary_insert()返回 BSTNode这是根，这称为 setter对于 root , 这是 -

@root.setter
def root(self,value):
    self._root = BSTNode(value)

这会导致 self._root用新的 BSTNode 初始化与从 binary_insert() 返回的根数据相同的引用, 这称为 __init__()对于 BSTNode传入 root作为论据。和 __init__() BSTNode的功能这样做 -

def __init__(self,new):
    if type(new) is BSTNode:
        self._data = new.data
    else:
        self._data = new
    self._left = None
    self._right = None

在这里，您正在设置 self._left至 None和 self._right至 None .因此，正如您所观察到的，根的左值和右值都没有。

有两种方法可以解决这个问题，一种是 -

更改您设置的行 self.root到 -

def binary_insert(self,list_in):
    self._root = binary_insert(list_in,0,len(list_in) - 1)

---

或者您也可以更改 __init__() BSTNode ，如果 type(new)是BSTNode ，你复制了left和 right来自 new 的值BSTNode以及。示例 -

def __init__(self,new):
    if type(new) is BSTNode:
        self._data = new.data
        self._left = new.left
        self._right = new.right
    else:
        self._data = new
        self._left = None
        self._right = None