二叉搜索樹的刪除方法什麼都不做

Question

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

def contains(root, value): 
    if root is None: 
     return False 

    if value == root.data: 
     return True 

    if value < root.data: 
     return contains(root.left, value) 
    else: 
     return contains(root.right, value) 


def insert(root, value): 
    if root is None: 
     root = BinaryNode(value) 
    else: 
     if value > root.data: 
      if root.right is None: 
       root.right = BinaryNode(value) 
      else: 
       return insert(root.right, value) 
     else: 
      if root.left is None: 
       root.left = BinaryNode(value) 
      else: 
       return insert(root.left, value) 

def getMin(root): 
    if root.left is None: 
     return root.data 
    return getMin(root.left) 

def remove(root, value, parent = None): 
    if root is None: 
     return False 
    elif value < root.data and root.left is not None: 
     return remove(root.left, value, root) 
    elif value > root.data and root.right is not None: 
     return remove(root.right, value, root) 
    else: 
     if parent.left is not None and parent.right is None and \ 
      root.left is None and root.right is None: 
       root = None 
       parent.left = root 



def inorder(root): 
    if root is not None: 
     inorder(root.left) 
     print(root.data) 
     inorder(root.right) 


b = BinaryNode(10) 
insert(b, 8) 
insert(b, 11) 

remove(b,11) 

inorder(b) 

我正在編寫我的二分查找樹的刪除函數，我100％肯定它是正確的實現邏輯明智。我已經實現了刪除葉節點的最基本的情況。這個問題必須是python相關的？當我嘗試刪除11時，它仍然在inorder遍歷中打印它。

Answer 1

刪除節點的邏輯缺少必要的步驟。請在下面找到刪除節點的代碼：

def remove(root, value, parent): 
    if root is None: 
     return False 
    elif value < root.data and root.left is not None: 
     return remove(root.left, value, root) 
    elif value > root.data and root.right is not None: 
     return remove(root.right, value, root) 
    else: 
     if value == root.data: 
      if root.right is not None: 
       removeRoot = root.right 
       while(removeRoot.left is not None): 
        parRoot = removeRoot 
        removeRoot = removeRoot.left 
       root.data = removeRoot.data 
       parRoot.left = None 
       del removeRoot 
      elif root.left is not None: 
       parent.left = root.left 
       del root 
      else: 
       if parent.right is not None and parent.right.data == root.data: 
        parent.right = None 
       elif parent.left is not None: 
        parent.left = None 
       del root