바이너리 검색 트리 : 삽입 기능에서 포인터가 손실 됨

Question

BST가있는 프로젝트를 수행 할 때 삽입 기능의 어딘가에 논리 오류가 있습니다. 찾을 수없는 것 같습니다.

삽입 기능 : 하나 개의 노드를 삽입하면 작동이 기능을 사용하여

int bst_insert (bst_t *tree, bst_key_t key) 
{ 
    bst_node_t *node, *temp_node; 
    if(tree == NULL) { 
    printf("Invalid tree pointer.\n"); 
    return; 
    } 
    if(tree->root == NULL) { 
    node = (bst_node_t *)malloc(sizeof(bst_node_t)); 
    node->left = node->right = NULL; 
    node->key = key; 
    tree->root = node; 
    return 1; 
    } 
    temp_node = tree->root; 
    while(1) { 
    if(temp_node == NULL) { 
     node = (bst_node_t *)malloc(sizeof(bst_node_t)); 
     node->left = node->right = NULL; 
     node->key = key; 
     temp_node = node; 
     return 1; 
    } 
    if(temp_node->key == key) { 
     temp_node->data_ptr = data; 
     return 0; 
    } else if(key < temp_node->key) { 
     temp_node = temp_node->left; 
    } else if(temp_node->key < key) { 
     temp_node = temp_node->right; 
    } 
    } 
} 

, 잘합니다 (트리 -이> 루트가 null, 그래서 그 if 문 안에 종료 아마 때문에),하지만 난 때와 두 번째를 삽입하고이 함수를 그대로두면 트리에는 첫 번째 노드 만 있습니다.

관련 정보를 제공하는 것을 잊어 버린 경우 알려주십시오.

Answer 1

문제는 여기에 있습니다 : 당신은 두 번째 과제를 수행 할 때, 실제로 temp_node가 가리키는 된 노드 영향을 미친다는 것을 가정하고

temp_node = tree->root; 
... 
temp_node = node; 

. 그러나 실제로는 다른 것을 변경하지 않고 temp_node의 내용을 대체합니다 (로컬 변수).

하나의 해결책은 "노드 포인터"에 대한 포인터를 갖는 것입니다. 그런 다음이 포인터가 가리키는 값을 변경하면 실제로는 지역 변수를 변경하는 대신 "세계를 변경하는 것"입니다. 같은 뭔가 :

bst_node_t **temp_node; 
... 
temp_node = &tree->root; 

/* To change the value that temp_node is pointing to */ 
*temp_node = node; 

/* To change temp_node itself */ 
... 
} else if(key < temp_node->key) { 
    temp_node = &temp_node->left; 
} else if(temp_node->key < key) { 
    temp_node = &temp_node->right; 
} 

포인터 - 투 - 포인터를 사용하지 않고이 문제를 해결하는 것이 가능하지만 다음 이전 (부모) 포인터를 기억 유지해야하고, 당신이 left 또는 right을 변경해야하는지 여부.