BST递归删除和中序遍历

Question

我正在实现一个二叉搜索树，我不确定我尝试添加、删除然后通过遍历显示的所有值是否都在那里。首先，对于 insert_element，我似乎只得到了我添加的第一个或两个值（不确定其他值的去向......）。我也不确定我的删除是否真的删除了任何东西。我试图通过按顺序遍历树来检查，但我不确定发生了什么，我收到以下错误消息：TypeError: str returned non-string (type __BST_Node).这是我的代码：

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

如果有人可以指出我在 logic/reasoning 和代码中的错误，或者可以给我任何关于如何正确遍历树的提示，我将不胜感激！另外，这是我使用的测试代码：

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

看起来你大部分都做对了，但是有一些逻辑错误。我修改了代码让你看看。

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

输出是

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

BST递归删除和中序遍历

recursive deletion from BST and in-order traversal

algorithm

python-3.x

binary-search-tree

recursive-datastructures