在Python中與遞歸和屬性設置器混淆

我試圖實現一個二進制搜索樹類。我有兩堂課; BSTNode和BST。我試圖強制執行的制定者搜索樹屬性left和right：在Python中與遞歸和屬性設置器混淆

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

這裏是我的功能（注意實例方法binary_insert上述BST類）：

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，這是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

來源

2015-07-12 wdonahoe

您能否澄清您的實際問題是什麼？輸出的哪一部分是你不期望的，你期望它是什麼？ – BrenBarn

@BrenBarn：編輯。 – wdonahoe

出現該問題，因爲所有的遞歸完成和根創建爲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作爲參數。和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。因此，根據您的觀察，根的左右值都不是。

兩種方法可以解決這個問題，一個是 -

改變你在哪裏設置self.root到線 -

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

或者你也可以改變__init__() BSTNode，例如如果type(new)爲BSTNode，則也可以複製newBSTNode中的left和right值。示例 -

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

來源

2015-07-12 18:25:04

現在好像很明顯！謝謝。 – wdonahoe

它看起來像您的插入方法正在構建樹，但它不附加到根，並且對樹的所有引用正在丟失。

順便說一下，請注意，您的平衡樹的方法（選擇列表分區的中間）只適用於列表排序。您需要事先對列表進行排序，或者使用更一般的平衡方案，如AVL樹或紅黑樹

來源

2015-07-12 18:27:10 ozymandias

在Python中與遞歸和屬性設置器混淆

回答

相關問題