rekursives Löschen von BST und In-Order-Traversal

Question

Ich bin ein binärer Suchbaum implementieren und ich bin mir nicht sicher, ob alle Werte, die ich hinzufügen, löschen und dann über Traversal anzeigen möchten, alle da sind. Erstens, für das insert_element scheint ich nur die ersten ein oder zwei Werte zu bekommen, die ich hinzufüge (nicht sicher, wohin die anderen gehen ...). Ich bin mir auch nicht sicher, ob meine Entfernung tatsächlich etwas entfernt. Ich habe versucht, dies zu überprüfen, indem ich den Baum in der richtigen Reihenfolge durchquerte, aber ich bin mir nicht sicher, was passiert und ich bekomme folgende Fehlermeldung: TypeError: str hat nicht-string zurückgegeben (Typ __BST_Node). Hier ist mein Code:

class Binary_Search_Tree: 
    class __BST_Node: 
    def __init__(self, value): 
     self.value = value 
     self.right_child = None 
     self.left_child = None 

    def __init__(self): 
    self.__root = None 
    self.__height = 0 
    self.value = None 

    def _recursive_insert(self, root, value): 
    new_stem = Binary_Search_Tree.__BST_Node(value) 
    if root is None: 
     root = new_stem 
     root.value = new_stem.value 
    else: 
     if root.value < new_stem.value: 
     if root.right_child is None: 
      root.right_child = new_stem 
      root.right_child.value = new_stem.value 
     else: 
      root = self._recursive_insert(root.right_child, value) 
     else: 
     if root.left_child is None: 
      root.left_child = new_stem 
      root.left_child.value = new_stem.value 
     else: 
      root = self._recursive_insert(root.right_child, value) 
    return root 

    def insert_element(self, value): 
    self.__root = self._recursive_insert(self.__root, value) 
    return self.__root 

    def _recursive_delete(self, root, value): 
    if root.value == value: 
     if root.right_child and root.left_child: 
      parent = root 
      replacement = root.right_child 
      while replacement.left_child: 
      parent = replacement 
      replacement = replacement.left_child 
      root.value = replacement.value 
      if parent.left_child == replacement: 
      parent.left_child = replacement.right_child 
     else: 
      parent.right_child = replacement.right_child 
     else: 
     if root.left_child: 
      return root.left_child 
     else: 
      return root.right_child 
    else: 
     if root.value > value: 
      if root.left_child: 
       root.left_child = self._recursive_delete(root.left_child, value) 
     else: 
     if root.right_child: 
      root.right_child = self._recursive_delete(root.right_child, value) 
    return root 

    def remove_element(self, value): 
    self.__root = self._recursive_delete(self.__root, value) 
    return self.__root 

    def traverse_in_order(self, root): 
    s = '[ ' 
    if root is not None: 
     self.traverse_in_order(root.left_child) 
     s += str(root.value) + ', ' 
     self.traverse_in_order(root.right_child) 
    s += ' ]' 
    return root 

    def in_order(self): 
    self.__root = self.traverse_in_order(self.__root) 
    return self.__root 

Wenn jemand zeigen kann, wo ich mich nicht irre in meiner Logik/Begründung und Code oder geben Sie mir irgendwelche Tipps, wie man richtig den Baum durchqueren wäre ich dankbar! Auch hier ist der Testcode war ich mit:

if __name__ == '__main__': 
    new = Binary_Search_Tree() 
    new.insert_element(23) 
    new.insert_element(42) 
    new.insert_element(8) 
    new.insert_element(15) 
    new.insert_element(4) 
    new.insert_element(16) 
    new.remove_element(16) 
    new.in_order() 
    print(new) 

Answer 1

aussehen wie Sie haben die meisten es richtig, aber einige logische Fehler gemacht. Ich habe den Code für Sie geändert, um einen Blick darauf zu werfen.

class Binary_Search_Tree: 
    class __BST_Node: 
    def __init__(self, value): 
     self.value = value 
     self.right_child = None 
     self.left_child = None 

    def __init__(self): 
    self.root = None 
    self.height = 0 
    self.value = None 

    def _recursive_insert(self, root, value): 
    new_stem = Binary_Search_Tree.__BST_Node(value) 
    if self.root is None: 
     self.root = new_stem 
     self.root.value = new_stem.value 
    else: 
     if root.value < new_stem.value: 
     if root.right_child is None: 
      root.right_child = new_stem 
      root.right_child.value = new_stem.value 
     else: 
      self._recursive_insert(root.right_child, value) 
     else: 
     if root.left_child is None: 
      root.left_child = new_stem 
      root.left_child.value = new_stem.value 
     else: 
      self._recursive_insert(root.left_child, value) 


    def insert_element(self, value): 
    self._recursive_insert(self.root, value) 


    def _recursive_delete(self, root, value): 
    if root.value == value: 
     if root.right_child and root.left_child: 
      parent = root 
      replacement = root.right_child 
      while replacement.left_child: 
      parent = replacement 
      replacement = replacement.left_child 
      root.value = replacement.value 
      if parent.left_child == replacement: 
      parent.left_child = replacement.right_child 
      else: 
      parent.right_child = replacement.right_child 
     else: 
     if root.left_child: 
      return root.left_child 
     else: 
      return root.right_child 
    else: 
     if root.value > value: 
      if root.left_child: 
       root.left_child = self._recursive_delete(root.left_child, value) 
     else: 
     if root.right_child: 
      root.right_child = self._recursive_delete(root.right_child, value) 
    return root 

    def remove_element(self, value): 
    self.root = self._recursive_delete(self.root, value) 
    return self.root 

    def traverse_in_order(self, root): 
    if root is None: 
     return 
    else: 
     self.traverse_in_order(root.left_child) 
     print root.value 
     self.traverse_in_order(root.right_child) 


    def in_order(self): 
    print "print in order:" 
    self.traverse_in_order(self.root) 


if __name__ == '__main__': 
    new = Binary_Search_Tree() 
    new.insert_element(23) 
    new.insert_element(42) 
    new.insert_element(8) 
    new.insert_element(15) 
    new.insert_element(4) 
    new.insert_element(16) 
    new.in_order() 
    new.remove_element(16) 
    new.in_order() 

Der Ausgang ist

print in order: 
4 
8 
15 
16 
23 
42 
print in order: 
4 
8 
15 
23 
42