Suppression récursive de BST et traversée dans l'ordre

Question

J'implémente un arbre de recherche binaire et je ne suis pas sûr que toutes les valeurs que j'essaie d'ajouter, de supprimer et d'afficher via traversal y soient toutes. Premièrement, pour l'élément insert_element, il semble que j'obtiens seulement la première ou les deux premières valeurs que j'ajoute (je ne sais pas exactement où vont les autres ...). Je ne suis pas sûr que mon retrait enlève quoi que ce soit. J'ai essayé de vérifier en traversant l'arbre dans l'ordre, mais je ne suis pas sûr de ce qui se passe et j'obtiens le message d'erreur suivant: TypeError: str retourné non-chaîne (type __BST_Node). Voici mon 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 

Si quelqu'un peut point où je me trompe dans ma logique/raisonnement et code ou peut me donner des conseils sur la façon de traverser correctement l'arbre, je serais reconnaissant! En outre, voici le code de test que j'utilisais:

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

Regardez comme vous avez la plupart de droite, mais a fait quelques bugs logiques. J'ai modifié le code pour que vous jetiez un coup d'oeil.

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() 

La sortie est

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