BST에서 노드를 삭제할 때 오류가 발생했습니다.

Question

이것은 진정으로 저를 곤경에 빠뜨렸습니다. 도시 이름으로 정렬 된 도시의 이진 검색 트리가 있습니다. 도시에는 인구와 GPS 좌표도 포함됩니다. 도시 이름 또는 도시 좌표로 트리에서 노드를 제거 할 수 있기를 원합니다. 이름이 잘 작동하지만 GPS 좌표가 작동하지 않습니다.

GPS로 노드를 제거하면 이진 트리를 인쇄하려고 할 때 스택 오버플로가 발생합니다. 아래는 내 코드 중 일부입니다. 같은 삭제 방법을 사용하고 있기 때문에 좌표로 삭제해도 이름으로 삭제해도 정상적으로 작동하는 것을 이해할 수는 없습니다.

정확한 오류는 "처리되지 않은 0x013214D6 예외 : 0xC00000FD : 스택 오버플로 (매개 변수 : 0x00000001, 0x00152FFC)"입니다. 이것은 좌표로 삭제 한 후 내 인쇄 기능에서 발생하지만 이름으로 삭제하는 경우에는 발생하지 않습니다.

bool BinaryTree::DeleteByName(string city) 
{ 
    if (GetRoot() != NULL) 
    { 
     return (DeleteByName(GetRoot(), city)); 
    } 
    return false; 
} 

TreeNode* BinaryTree::DeleteByName(TreeNode *node, string city) 
{ 
    if (node == NULL) 
    { 
     return node; 
    } 
    else if (city < node->Data.name) 
    { 
     node->Left = DeleteByName(node->Left, city); 
    } 
    else if (city > node->Data.name) 
    { 
     node->Right = DeleteByName(node->Right, city); 
    } 
    else 
    { 
     if (node->Left == NULL && node->Right == NULL) 
     { 
      delete node; 
      node = NULL; 
     } 
     else if (node->Left == NULL)   
     { 
      TreeNode* temp = node; 
      node = node->Right; 
      delete temp; 
     } 
     else if (node->Right == NULL) 
     { 
      TreeNode* temp = node; 
      node = node->Left; 
      delete temp; 
     } 
     else 
     { 
      cout << "Else"; 
      TreeNode* temp = MinPtr(node->Right); 
      node->Data = temp->Data; 
      node->Right = DeleteByName(node->Right, temp->Data.name); 
     } 
    } 
    return node; 
} 

bool BinaryTree::DeleteByCoord(pair<double, double> coords) 
{ 
    if (GetRoot() == NULL) 
    { 
     return false; 
    } 
    else 
    { 
     return DeleteByCoord(GetRoot(), coords); 
    } 
} 

bool BinaryTree::DeleteByCoord(TreeNode* node, pair<double, double> coords) 
{ 
    bool result; 

    if (node == NULL) 
    { 
     return false; 
    } 
    else 
    { 
     if (node->Data.coordinates.first == coords.first && node->Data.coordinates.second == coords.second) 
     { 
      return (DeleteByName(node, node->Data.name));   
     } 

     result = DeleteByCoord(node->Left, coords); 
     if (result == true) 
     { 
      return result; 
     } 

     return DeleteByCoord(node->Right, coords); 
    } 
} 




void BinaryTree::Insert(City city) 
{ 
    TreeNode* temp = new TreeNode(city); 
    if (GetRoot() == NULL) 
    { 
     root = temp; 
    } 
    else 
    { 
     Insert(temp, GetRoot()); 
    } 
} 

void BinaryTree::Insert(TreeNode* toAdd, TreeNode* addHere) 
{ 
    if (toAdd->Data < addHere->Data) 
    { 
     if (addHere->Left != NULL) 
     { 
      Insert(toAdd, addHere->Left); 
     } 
     else 
     { 
      addHere->Left = toAdd; 
     } 
    } 
    else if (toAdd->Data > addHere->Data) 
    { 
     if (addHere->Right != NULL) 
     { 
      Insert(toAdd, addHere->Right); 
     } 
     else 
     { 
      addHere->Right = toAdd; 
     } 
    } 
} 

void BinaryTree::InOrderTraversal(TreeNode* node) 
{ 
    if (node != NULL) 
    { 
     InOrderTraversal(node->Left); 
     cout << node->Data << endl; 
     InOrderTraversal(node->Right); 
    } 
} 

void BinaryTree::InOrderTraversal() 
{ 
    InOrderTraversal(GetRoot()); 
} 

TreeNode* BinaryTree::GetRoot() 
{ 
    return root; 
} 

TreeNode* BinaryTree::MinPtr(TreeNode* node) 
{ 
    while (node->Left != NULL) 
    { 
     node = node->Left; 
    } 
    return node; 
} 

Answer 1

노드를 삭제할 때 삭제 된 노드를 가리키는 상위 포인터를 업데이트해야합니다. 여기서주의 : 당신이 DeleteByName를 호출 할 때

직접이 필요한 노드를 검색하고 자동으로 부모 노드 포인터로 설정 NULL 포인터를 반환 부모의 Left

else if (city < node->Data.name) 
{ 
    node->Left = DeleteByName(node->Left, city); 
} 
else if (city > node->Data.name) 
{ 
    node->Right = DeleteByName(node->Right, city); 
} 

을하지만 좌표 방식에서 DeleteByName를 호출 할 때 재설정하지 않습니다를/Right 포인터 : DeleteByName 등의 차례로

if (node->Data.coordinates.first == coords.first && node->Data.coordinates.second == coords.second) 
{ 
    return (DeleteByName(node, node->Data.name));   
} 

이미 필요한 수신 노드는 재귀 칼을 수행하지 않습니다 L과 부모의 포인터를 재설정하지 않습니다 중 하나

else 
{ 
    if (node->Left == NULL && node->Right == NULL) 
    { 
     delete node; 
     node = NULL; 
    } 
    //... same here 
} 

참고 : 코드에 더 많은 문제가 있습니다. 눈을 공격하는 일부 :

• DeleteByName 반환 포인터하지만 DeleteByCoord 반환 bool, 당신은 직접 복식을 비교하는 DeleteByCoord
• 피에 부울 형식으로 포인터를 사용, 비교 결과가 잘못 될 수 있습니다. 자세한 내용은 question 및 explanation을 참조하십시오.