使用递归从二进制搜索树中删除节点

Question

因此，我试图通过使用类内的这两个函数从树中删除节点。不幸的是，它只是不删除任何内容，我想知道这是怎么回事！任何帮助将不胜感激。

def Find_Min(self,node):
        current=node
        while current.left is None:
             current=current.left
        return current



    def deletenode(self,node,ntbd):  ##ntbd:node to be deleted  /// node: root node
        if node is None:
            return None
        elif node.data>ntbd:
            node.left=self.deletenode(node.left,ntbd)
        elif node.data<ntbd:
            node.right=self.deletenode(node.right,ntbd)
        else:  ##Found you bastard
            if node.left==None and node.right==None:
                node=None
            elif node.left==None:
                temp=node.right
                node=None
                print("----",temp)
            elif node.right==None:
                temp=node.left
                node=None
                print("----",temp)
            else:
                smallest=self.Find_Min(node.right)
                node.data=smallest.data
                node.right=self.deletenode(node.right,smallest.data)

Answer 1

给出node-

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

让我们创建树t-

t = node \
  ( 1
  , node(2, node(3), node(4))
  , node(5, node(6), node(7))
  )

哪个代表这棵树-

       1
      / \
     /   \
    2     5
   / \   / \
  3   4 6   7

第一种打印树的方法，to_str-

def to_str (root = None):
  if not root:
    return ""
  else:
    return f"(node {root.data} {to_str(root.left)} {to_str(root.right)})"

print(to_str(t))
# (node 1 (node 2 (node 3  ) (node 4  )) (node 5 (node 6  ) (node 7  )))

现在是通往delete节点的方法-

def delete (root = None, q = None):
  if not root or root.data == q:
    return None
  else:
    return node(root.data, delete(root.left, q), delete(root.right, q))

print(to_str(t))
# (node 1 (node 2 (node 3  ) (node 4  )) (node 5 (node 6  ) (node 7  )))

print(to_str(delete(t, 2)))
# (node 1  (node 5 (node 6  ) (node 7  )))

通知delete返回一棵新树，并且不会破坏旧树-

print(to_str(t))
# (node 1 (node 2 (node 3  ) (node 4  )) (node 5 (node 6  ) (node 7  )))

print(to_str(delete(t, 2)))
# (node 1  (node 5 (node 6  ) (node 7  )))

print(to_str(delete(t, 3)))
# (node 1 (node 2  (node 4  )) (node 5 (node 6  ) (node 7  )))

print(to_str(t))
# (node 1 (node 2 (node 3  ) (node 4  )) (node 5 (node 6  ) (node 7  )))

---

如果您想将函数作为对象方法添加到某种tree类中-

def to_str (root = None):
  # defined above ...

def delete (root = None, v = None):
  # defined above ...

class tree:
  def __init__(self, root = None):
    self.root = root

  def __str__(self):
    return to_str(self.root)          # <--

  def delete(self, v = None):
    return tree(delete(self.root, v)) # <--

这为您提供了与更熟悉的面向对象界面相同的不变（持久）功能-

print(tree(t))
# (node 1 (node 2 (node 3  ) (node 4  )) (node 5 (node 6  ) (node 7  )))

print(tree(t).delete(2))
# (node 1  (node 5 (node 6  ) (node 7  )))

print(tree(t).delete(3))
# (node 1 (node 2  (node 4  )) (node 5 (node 6  ) (node 7  )))

print(tree(t))
# (node 1 (node 2 (node 3  ) (node 4  )) (node 5 (node 6  ) (node 7  )))