이진 검색 트리에 대한 제거 방법이 없습니다.

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 % 확실합니다. 리프 노드를 삭제하는 가장 기본적인 경우를 구현했습니다. 문제는 파이썬과 관련이 있습니까? 11을 지우려고하면 inorder traversal에서 여전히 11을 인쇄합니다.

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