问题有二叉搜索树在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

回答

相关问题