이진 트리에서 리프 노드를 삭제하십시오.

Question

바이너리 검색 트리에서 leaf node을 삭제하려고하는데 저에게 맞지 않습니다. 코드가 디버깅되어 문제를 찾을 수 없습니다. 나는 흐름이 정확하다는 것을 볼 수 있고, 전화는 leaf node 주소에 도달하고, free을 호출한다. 하지만 그 후 나는 pre-order을 통과 할 때 가치가 여전히 존재한다는 것을 알게됩니다.

진 나무는 내가 (그 간단한 일) 생성 - = 14 삭제 될

      10 
         / \ 
         6  14 

Leaf Node 값을; 삭제 Pre - order 탐색 결과 전

= 10->6->14. 이것은 내 콘솔에 인쇄되어 있습니다.

// Delete a leaf node 

void deleteNode(struct Nodes * root,int value){ 

    // Check if root is null 

    if (root == NULL) { 
     return; 
    } 

    // If no left and right node present, it's a leaf node. Perform delete. 

    while (root->left == NULL && root->right == NULL) { 

     // Check if value at leaf node is same as value to be deleted. If yes, go inside (if). 

     if (root->info == value) { 
      printf("Delete the leaf node \n"); 

      printf("delete node address is \n %p",root); 

      // free the root (which is currently a leaf node) 
      free(root); 
      return; 
     } 
    } 

    // keep checking if value to be deleted is on right or left, till a value is found. 

    if (root->info < value) { 
     // Ccheck on right 
     deleteNode(root->right,value); 
    }else{ 
     // check on left 
     deleteNode(root->left,value); 
    } 

} 

내가 어떤 errors하지 않는, 그래서 내가 근본 원인를 추측 할 수없는입니다 : -

코드 leaf node은 삭제합니다. 삭제 Pre - order 탐색 결과 후

= 10->6->14. 누구든지 나를 도울 수 있습니까? 나는 매우 어리석은 실수를하고 있다는 것을 알고있다, 또는 나의 개념은 아직도 맑지 않다. 감사합니다.

기타 정보가 필요한 경우 알려 주시기 바랍니다.

출력 이미지 : 올바른 값과 동일한 주소를 볼 수 있습니다.

Answer 1

free는 "나는 그것이 free되기를 임의로 할당 할 수있는 더 많은 메모리를 사용하지 않을 것을 맹세한다"꽤 많은 것을 의미한다.

당신은 그 약속을 위반하고 있습니다. 메모리를 비우고 나면 해당 주소의 모든 참조도 잊어 버려야합니다. 부모 노드는 여전히 노드가 있던 곳의 주소를 기억하고 우연히 메모리가 아직 재활용되지 않았습니다.

당신은 오류 전형적인 "확보 한 후 사용을"이있다. 그 사이에 다른 노드를 할당했다면, 다시 트래버스하기 전에 메모리 손상을 발견했을 것입니다.

부모 개체의 포인터를 가리키는 매개 변수를 함수에 하나 이상 추가 할 수 있습니다. 그렇게하면 부모를 수정할 수 있습니다.

노드의 부모에게 다시 참조를 저장하십시오.

어느 것이 든 작동합니다.

Answer 2

한 가지 방법은 재귀 호출의 부모에게 포인터를 전달하는 것입니다.

void deleteNode(struct Nodes *root, struct Nodes *parent, int value){ 

    // Check if root is null 

    if (root == NULL) { 
     return; 
    } 

    if ((root->info == value) && (root->left == NULL) && (root->right == NULL)) { 
     if (parent->left->info == value) {free(parent->left); parent->left = NULL;} 
     else {free(parent->right); parent->right = NULL;} 
    } 
    else if (root->info < value) { 
     // check on right 
     deleteNode(root->right,root, value); 
    }else{ 
     // check on left 
     deleteNode(root->left,root, value); 
    } 
}