이진 검색 트리 내가 BST의 구현 다음 한 이전

Question

에 어떤 포인터 노드를 삭제. 메소드 추가/구현 구현에는 아무런 문제가 없지만 구조에서 노드를 제거하는 방법을 알 수는 없습니다. 왼쪽 및 오른쪽 노드에 대한 포인터 만 가지고있을 때 어떤 가능성이 있습니까? 모든 방법은 구조체에 구현되어야하며, (교사로부터받은 작업 때문에) BstNode 구조체가 아니라는 점에 유의하십시오. 이 같은

Answer 1

뭔가, 특정 요구 사항에 적응하고 당신은 당신의 데이터 구조에서 부모 포인터가없는

void remove(BstTree& tree, int value) 
{ 
    BstNode* parent = nullptr; 
    BstNode* node = tree.root; 
    while (node) 
    { 
     if (node->value == value) 
     { 
     if (parent) 
     { 
      // remove node using the parent pointer 
     } 
     else 
     { 
      // remove the root node 
     } 
     return; 
     } 
     if (value < node->value) 
     { 
     // go down left branch 
     parent = node; 
     node = node->leftSubNode; 
     } 
     else 
     { 
     // go down right branch 
     parent = node; 
     node = node->rightSubNode; 
     } 
    } 
}