Löschen der Operation in der grundlegenden Implementierung der binären Suchstruktur in Python

Question

Ich bin fast fertig mit meiner Binary Search Tree-Implementierung in Python mit Ausnahme der Löschoperation.

Bisher in allen Anwendungsfällen der Funktion, die ich bisher getestet haben: 1. Blattknoten sind, werden gelöscht richtig 2. Knoten mit zwei Kindern gelöscht richtig 3. Wurzelknoten korrekt

gelöscht

aber ich bin nicht in der Lage, Knoten mit dem linken Kind oder dem rechten Kind zu löschen. Meine Eclipse-IDE zeigte mir, dass einige der Aussagen keine Wirkung haben (die Aussagen, die im folgenden Bild gelb unterstrichen sind), also habe ich das Programm auf meinem lokalen iPython Notebook-Server ausprobiert, aber das Ergebnis scheint dasselbe zu sein.

Zeilen 43-57:

was ist es, dass ich in meinem Python-Programm bin verpassen? bitte hilf mir. Hier ist mein Code:

prevnode = None 

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

def insert(node,info): 
    if node.data is None: 
     node.data = info 
    elif info < node.data: 
     if node.left is None: 
      node.left = Node(None) 
     insert(node.left,info) 
    elif info >= node.data: 
     if node.right is None: 
      node.right = Node(None) 
     insert(node.right,info) 

def search(node,info): 
    if node is None: 
     print "Node with the mentioned data is not found" 
    if node.data == info: 
     print "Found the node containing value held by info" 
    elif info < node.data and node.left is not None: 
     search(node.left,info) 
    elif info > node.data and node.right is not None: 
     search(node.right,info) 

def delete(node,info): 
    global prevnode 
    if info == node.data: 
     print "This is the place where info is stored" 
     if node.left is None and node.right is None: 
      if prevnode.left is not None and prevnode.left.data == node.data: 
       prevnode.left = None 
       del node 
      elif prevnode.right is not None and prevnode.right.data == node.data: 
       prevnode.right = None 
       del node 
      return     
     elif node.left is not None and node.right is None: 
      if prevnode.left is not None and prevnode.left.data == node.data: 
       prevnode.left == node.left 
       del node 
      elif prevnode.right is not None and prevnode.right.data == node.data: 
       prevnode.right == node.left 
       del node 
      return 
     elif node.left is None and node.right is not None: 
      if prevnode.left is not None and prevnode.left.data == node.data: 
       prevnode.left == node.right 
       del node 
      elif prevnode.right is not None and prevnode.right.data == node.data: 
       prevnode.right == node.right 
       del node 
      return   
     elif node.left is not None and node.right is not None: 
      node.data = None 
      prevnode = node.right 
      successor = prevnode.left 
      if successor is None: 
       node.data = prevnode.data 
       node.right = prevnode.right 
      elif successor is not None: 
       while successor.left is not None: 
        prevnode = successor 
        successor = prevnode.left 
       if successor.right is None: 
        node.data = successor.data 
        prevnode.left = None 
        del successor 
       elif successor.right is not None: 
        prevnode.left = successor.right 
        node.data = successor.data 
        successor.right = None 
        del successor    
    elif info < node.data: 
     print "We will have to go to the left child of the current node" 
     prevnode = node 
     print "parent of the left child will be prevnode : ",prevnode.data 
     delete(node.left,info) 
    elif info >= node.data: 
     print "We will have to go to the right child of the current node" 
     prevnode = node 
     print "parent of the right child will be prevnode : ",prevnode.data 
     delete(node.right,info) 

def display(node,parent): 
    if node is not None: 
     print "value at this node is ",node.data 
     if parent is None: 
      print "it is the root node" 
     else: 
      print "the parent is ",parent.data 
    if node.left is not None: 
     display(node.left,node) 
    if node.right is not None: 
     display(node.right,node) 
    else: 
     return 

BST = Node(None) 
while True: 
    choice = int(raw_input("Please enter your choice 1.Insert, 2.Search, 3.Delete, 4.Display, 5.Exit")) 
    if choice == 1: 
     num = int(raw_input("Please enter the number you wish to insert")) 
     insert(BST,num) 
    elif choice == 2: 
     num = int(raw_input("Please enter the number you wish to find")) 
     search(BST,num) 
    elif choice == 3: 
     num = int(raw_input("Please enter the number you wish to delete")) 
     delete(BST,num) 
    elif choice == 4: 
     print "Displaying the Tree" 
     display(BST,None) 
    elif choice == 5: 
     break 
    else: 
     print "Please enter the correct input" 

P. S: nur für den Fall es irgendwelche falschen Vertiefungen (Ich bin ziemlich sicher, es gibt keine though), können sie richtig eingerückt

Answer 1

Es gibt einen einfachen Tippfehler. Du verwendest == statt =.

Anstatt also diese:

elif node.left is not None and node.right is None: 
     if prevnode.left is not None and prevnode.left.data == node.data: 
      prevnode.left == node.left 
      del node 
     elif prevnode.right is not None and prevnode.right.data == node.data: 
      prevnode.right == node.left 
      del node 
     return 
    elif node.left is None and node.right is not None: 
     if prevnode.left is not None and prevnode.left.data == node.data: 
      prevnode.left == node.right 
      del node 
     elif prevnode.right is not None and prevnode.right.data == node.data: 
      prevnode.right == node.right 
      del node 
     return 

Sie wollen, dies zu tun:

elif node.left is not None and node.right is None: 
     if prevnode.left is not None and prevnode.left.data == node.data: 
      prevnode.left = node.left # Changed == to = 
      del node 
     elif prevnode.right is not None and prevnode.right.data == node.data: 
      prevnode.right = node.left # Changed == to = 
      del node 
     return 
    elif node.left is None and node.right is not None: 
     if prevnode.left is not None and prevnode.left.data == node.data: 
      prevnode.left = node.right # Changed == to = 
      del node 
     elif prevnode.right is not None and prevnode.right.data == node.data: 
      prevnode.right = node.right # Changed == to = 
      del node 
     return