루트 포인터로 가리키는 이진 탐색 트리에서 데이터를 제거하십시오.

Question

이중 포인터를 사용하여 BST에서 데이터를 제거한 다음 필요한 경우 루트를 변경하는 방법을 파악하는 데 많은 어려움이 있습니다. 이것은 내가 시도하는 것입니다. 그러나 테스트 할 때 제거해서는 안되는 숫자를 제거합니다 ... 결함이 무엇인지에 대한 아이디어가 있습니까?

편집 : 아래는 내가 문제가 라인 *rootRef = tmp->left;에있다 생각 대답 한 후 내 새로운 코드 ...

int removeBST(struct TreeNode** rootRef, int data) 
    { 

     while (*rootRef && (*rootRef)->data != data) 
     { 

     if ((*rootRef)->data > data) 
     { 

      rootRef = &(*rootRef)->left; 
     } 
     else if ((*rootRef)->data < data) 
     { 
       rootRef = &(*rootRef)->right; 
     } 
    } 

    if (*rootRef) 
    { 
     struct TreeNode *tmp = *rootRef; 
     if (rootRef->left == NULL && rootRef->right == NULL) // no children 
     { 
     free(tmp); 
     } 
     else if (rootRef->left->left == NULL && rootRef->right->right == NULL) // one child 
{ 
    rootRef = rootRef->left; 
} 
else 
{ 
    rootRef = inOrderSuccessor(rootRef); 
    removeBST(**rootRef, data); 
} 

     return 1; 
    } 

    return 0; 

} 

Answer 1

입니다.

이 줄은 노드 rootRef을 삭제하려고 시도합니다. 실제로 노드가 왼쪽 자식으로 바뀝니다. 이는 rootRef에만 자식이 인 경우 올바릅니다. 그러나 올바른 차일드가있는 경우 고아이됩니다. 다음과 같이 당신이해야 할 일은

가 제대로 삭제를 처리 할 수 ​​있습니다 : rootRef가 아이가없는

1. 경우, 즉, rootRef->left == NULL && rootRef->right == NULL, 단순히 노드를 제거합니다. rootRef이 하나의 아이이있는 경우

2. , 그 아이 rootRef를 교체합니다.

3. 는 rootRef가 두 아이가있는 경우, 그 in-order 후계자로 rootRef의 값을 대체, 당신이 경우 1 또는 2

An example on removing a node from a BST에 도달 할 때까지 해당 노드 반복적으로을 삭제합니다.

코드는 다음에 비슷한 모양해야합니다

int removeBST(struct TreeNode** rootRef, int data) { 
    while (*rootRef && (*rootRef)->data != data) { 
     ... 
    } 


    struct TreeNode* prootRef = *rootRef; 
    if (prootRef) { 
     if(prootRef->left && prootRef->right) // Both children exist 
      // Find its in-order successor 
      ... 
     } 
     else if(prootRef->left) { // Only left child exists 
      // Replace rootRef by its left child 
      ... 
     } 
     else if(prootRef->right) { // Only right child exists 
      // Replace rootRef by its right child 
      ... 
     } 
     else { // rootRef is a leaf node 
      // Delete rootRef 
      ... 
     } 

     return 1; 
    } 

    return 0; 
}