C++ 이진 검색 트리 삭제

Question

그래서 내 질문은 왜 이것이 작동하지 않는지 이해할 수 없습니다. 나는 분명히 부모가 결코 초기화되지 않는다고 말하는 곳 아래에 주석을 달았다. 나는 포인터를 잘못하고있는 것입니까, 나는 논리를 거꾸로 갖게 되었습니까? 나는 지금까지 그것을 처음부터 시작하는 것이 더 낫겠습니까? 이것은 내가 직면 한 가장 어려운 임무이므로 어떤 도움이라도 매우 유용 할 것입니다.

void Dictionary::remove(string word) 
{ 
if(root == NULL) 
{ 
    cout << "list is empty\n"; 
    return; 
} 
DictionaryNode *curr = root; 
DictionaryNode *parent = NULL;` 

while(curr != NULL) 
{ 
    if(curr->word == word) 
     break; 
    else 
    { 
     parent = curr; 
     if(word > curr->word) 
      curr = curr->right; 
     else 
      curr = curr->left; 
    } 
} 
//LEAF node. 
if(curr->left == NULL && curr->right == NULL) 
{ 
    if(parent->left == curr) // Right here is an access violation. Which doesn't //make sense. 
    { 
     parent->left = NULL; 
    } 
    else 
    { 
     parent->right = NULL; 
    } 
    delete curr; 
} 

/* 
* Node has a single child LEFT or RIGHT 
*/ 
if((curr->left == NULL && curr->right != NULL) || (curr->left != NULL && curr->right == NULL)) 
{ 
    if(curr->left == NULL && curr->right != NULL) 
    { 
     if(parent->left == curr) //if(parent->left == curr) //says parent is //not intialized 
     { 
      parent->left = curr->right; 
      delete curr; 
     } 
     else 
     { 
      parent->right = curr->right; 
      delete curr; 
     } 
    } 

    else 
    { 
     if(parent->left == curr) 
     { 
      parent->left = curr->left; 
      delete curr; 
     } 
     else 
     { 
      parent->right = curr->left; 
      delete curr; 
     } 
    } 

} 

if (curr->left != NULL && curr->right != NULL) 
{ 
    DictionaryNode* temp; 
    if(parent == NULL || parent->left==curr) 
    { 
     temp = curr->right; 
     while(temp->left!=NULL) 
      temp = temp->left; 
     if(parent!=NULL) 
      parent->left = curr->right; 
     else 
      root = curr->right; 
     temp->left = curr->left; 
     curr->left = curr->right=NULL; 
     delete curr; 

    } 

    else if(parent->right==curr) 
    { 
     temp = curr->left; 
     while(temp->right!=NULL) 
      temp = temp->right; 
     parent->right=curr->left; 
     temp->right = curr->right; 
     curr->left = curr->right=NULL; 
     delete curr; 
    } 
    } 

} 

Answer 1

1. 우선 나는 참조 :

기록 된대로

while(curr != NULL) 
{ 
//stuff 
} 

것 같습니다 당신의 루프 CURR == NULL의 끝에

게으른 나를보고했다 당신의 루프의 내용은 휴식을 알 수 있습니다. 루프에서 더 큰 블록을 사용하면 중단이 눈에 띄지 않을 수 있습니다. 이것은 좋은 습관이 아닙니다.

bool (예 : bool isNodeFound;)을 사용하면 값이 싸고 (1 비트) 더 명확하게 나타납니다. while (curr! = NULL & &! isNodeFound) 루프의 내용을 보지 않고 처음에는 의도가 분명하지 않습니다.

2. 실제로 루프에서 휴식 시간에 맞지 않고 curr == NULL이라면? 다음 명령 curr-> left가 실패합니다! 부울처럼 보입니다.

if(!isNodeFound) 
{ 
//log error if you can "cannot remove node because it is not in dictionary" 
return false; //make your function a bool to return if it succeeded or not 
} 

봅니다 작동하는지 알려주세요, 마음의 동일한 상태보다 선명도와 테스트와 코드의 나머지 부분을 분석합니다.