問題有二叉搜索樹在Python

-2

我努力學習二叉搜索樹的實現在Python用以下鏈接Binary Search Tree in Python 問題有二叉搜索樹在Python

我無法正確地執行刪除方法的幫助下刪除方法。

這裏是我的代碼：

class Node: 
    def __init__(self,data): 
     self.data=data 
     self.left=None 
     self.right=None 

def Insert_BTreeNode(self,data): 
    if self.data: 
     if data<self.data: 
      if self.left is None: 
       self.left=Node(data) 
      else: 
       self.left.Insert_BTreeNode(data) 

     elif data>self.data: 
      if self.right is None: 
       self.right=Node(data) 

      else: 
       self.right.Insert_BTreeNode(data) 

    else: 
     self.data=data 

def Lookup(self,data,parent=None): 

    if data<self.data: 
     if self.left is None: 
      return None,None 
     return self.left.Lookup(data,self) 
    elif data>self.data: 
     if self.right is None: 
      return None,None 
     return self.right.Lookup(data,self) 
    else: 
     print(self.data,parent.data) 



def Children_count(self): 
    count=0 

    if self.left: 
     count+=1 
    if self.right: 
     count+=1 

    print(count) 

def Delete(self,data): 
    children_count=0 
    node=self.Lookup(data) 
    parent=None 

    if node is not None: 
     children_count=node.Children_count() 

    if children_count==0: 
     if parent: 
      if parent.left is Node: 
       parent.left=None 
      else: 
       parent.right=None 
      del Node 
     else: 
      self.data=data 

def print_treeInorder(self): 
    if self.left: 
     self.left.print_treeInorder() 
    print(self.data) 
    if self.right: 
     self.right.print_treeInorder() 


def print_treePostorder(self): 
    if self.left: 
     self.left.print_treePostorder() 
    if self.right: 
     self.right.print_treePostorder() 
    print(self.data) 

def print_treePreorder(self): 
    print(self.data) 

    if self.left: 
     self.left.print_treePreorder() 
    if self.right: 
     self.right.print_treePreorder() 

root=Node(8) 
root.Insert_BTreeNode(3) 
root.Insert_BTreeNode(10) 
root.Insert_BTreeNode(1) 
root.Insert_BTreeNode(6) 
root.Insert_BTreeNode(4) 
root.Insert_BTreeNode(7) 
root.Insert_BTreeNode(14) 
root.Insert_BTreeNode(13) 
root.Delete(13) 
root.print_treeInorder()

這是一種像功課，所以我會很感激，如果人們給我與我的代碼解決方案，而不是外部庫。

此外，我會很感激，如果任何人都可以評論哪裏的代碼是錯誤的。

在此先感謝。

來源

2017-03-14 Dhruv Marwha

你缺少在'一個else分支，如果children_count == 0' – Sekuraz

秒：函數'查找（）時，搜索到的節點被發現'不返回一對夫婦'（父，個體經營）''數據== self.data'。 –

第三：函數'Children_count（）'不返回'（count）'。 –

爲了讓功能class Node的Delete()正常工作時使用的"Blog: Binary Search Tree library in Python"提供的代碼，就必須糾正以下缺失和錯字錯誤。

第1步 - 從Lookup()函數返回預期的耦合（節點，父節點）。

正如上面評論和博客中描述的，當找到節點被刪除時，函數應該返回節點和父節點。父母仍然等於無時，請勿嘗試打印parent.data。

def Lookup(self,data,parent=None): 
    if data<self.data: 
     if self.left is None: 
      return (None,None) 
     return self.left.Lookup(data,self) 
    elif data>self.data: 
     if self.right is None: 
      return (None,None) 
     return self.right.Lookup(data,self) 
    else: 
     # prevent case of parent is None 
     if (parent is not None): 
      print(self.data,parent.data) 
     # ADDED from blog link 
     return (self, parent)

步驟2 - 從Children_count()函數返回的數量。

作爲評價上述和在博客中所描述的，功能Children_count()的結果應被返回到被考慮帳戶。

def Children_count(self): 
    count=0 
    if self.left: 
     count+=1 
    if self.right: 
     count+=1 
    print(count) 
    # ADDED from link 
    return (count)

步驟3 - 在Delete()功能管理從self.Lookup(data)返回值。

正如上面評論和博客中所述，返回的值爲 Lookup()是一對節點。

def Delete(self,data): 
    children_count=0 
    # INSERTED from link 
    node, parent = self.Lookup(data) 
    ...

代替：

def Delete(self,data): 
    children_count=0 
    node =self.Lookup(data) 
    parent=None 
    ...

步驟4 - Python是一個區分大小寫的語言，Node和node是不等價的。

正如上述評論，並在博客中描述，調用類的功能，就需要使用它的實例node，而不是它的類名Node的。

在這種情況下if children_count==0:：

if children_count==0: 
    print(" - The node to remove has no child.") 
    if parent: 
     # INSERTED from link 
     if parent.left is node: 
      parent.left=None 
     else: 
      parent.right=None 
     # INSERTED from link 
     del node 
    else: 
     self.data=data

相反的：

if children_count==0: 
    if parent: 
     if parent.left is Node: 
      parent.left=None 
     else: 
      parent.right=None 
     del Node 
    else: 
     self.data=data

什麼？

再利用博客的兩個elif children_count == 1:的源代碼（要去除的節點有1個小孩。）和else:（的節點，除去有2個孩子。）和函數Delete()將正常工作。

測試案例1 - 要移除的節點沒有子節點。

root.Delete(13)

測試案例2 - 要去除的節點有1個小孩。

root.Delete(10)

測試案例3 - 要去除的節點有2個孩子。

root.Delete(6)

測試案例4 - 要刪除的節點有2個孩子，是根節點。

root.Delete(8)

來源

2017-03-19 15:55:34

謝謝@ J.Piquard所有的提示。 –

問題有二叉搜索樹在Python

回答

相關問題