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

Question

我正在尝试实现二叉搜索树 class。我有两个 class； BSTNode，和 BST。我尝试在 setter 中为 left 和 right:

强制执行搜索树属性

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

这是我的函数（注意上面 class 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，尽管树中唯一的节点在函数运行s 是 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() returns一个BSTNode是根，这个调用setter为root，也就是-

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

这导致 self._root 被初始化为一个新的 BSTNode 引用，其数据与从 binary_insert() 返回的 root 的数据相同，这调用 __init__() for BSTNode 传入 root 作为参数。 BSTNode 的 __init__() 函数就是这样做的 -

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。所以根的左值和右值是 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

Answer 2

看起来你的插入方法正在构建一棵树，但它没有附加到根，所有对树的引用都将丢失。

顺便说一句，请注意您的树平衡方法（选择列表分区的中间部分）仅在列表已排序时才有效。您需要事先对列表进行排序或使用更通用的平衡方案，如 AVL 树或红黑树

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

Confusion with recursion and property setters in Python

python

recursion

binary-search-tree

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

Confusion with recursion and property setters in Python

python

recursion

binary-search-tree

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