K & R

Question

에서 이진 트리 구현 C 질문에서 K & RC 책을 통해 읽었으며 질문이 있습니다. 140-141 페이지의 6 장 구조체에 다음과 같은 코드가 있습니다 (나는 더 관련이없는 부분의 일부를했다)

/* 
the program loops through a tree looking for some word 
if it finds the word itll incremenet the count by 1 
if it doesnt itll add a new node 
*/ 

struct node { 
    char *word; 
    int count; 
    struct node *left; 
    struct node *right; 
} 

main() { 
    struct node *root; 
    char word[1000]; 

    root = NULL; 
    while(getword(word, MAXWORD) != EOF) /* getword just grabs 1 word at a time from a file of words */ 
     if(isalpha(word[0])) /* isalpha checks to see if it is a valid word */ 
      root = addNode(root, word); 

    treeprint(root); /* prints the tree */ 
    return 0; 
} 

struct node *addNode(struct node *p, char *w) { 
    int cond; 

    if(p == NULL) { 
     p = malloc(sizeof(struct node)); /* allocates memory for the new node */ 
     p -> word = strdup(w); 
     p -> count = 1; 
     p -> left = p -> right = NULL; 
    } 

    else if ((cond = strcmp(w, p -> word)) == 0) 
     p -> count++; 

    else if(cond < 0) 
     p -> left = addNode(p -> left, w); 

    else 
     p -> right = addNode(p -> right, w); 

    return p; 
} 

그리고 내 혼란이 루트 = addNode 명 (루트, 워드)

는 addNode 명 새로 추가에 대한 포인터를 반환하는 경우의 main() 함수에 노드 (또는 그 단어가 이미 int 인 경우 해당 노드에 있음)를 선택하면 트리 위의 모든 데이터가 "손실"되지 않습니까? 나무 뿌리로 머물러 있어야하지 않습니까?

감사합니다.

Answer 1

root은 항상 트리의 루트로 유지됩니다. root은 addNode의 첫 번째 매개 변수로 전달되며 NULL 인 경우에만 malloc이됩니다. 즉 root이 처음 전달 된 경우입니다. 이후 호출에서는 root을 변경하지 않고 count, left 또는 right 만 수정합니다. 재귀 addNode에서는 p이 전달되지 않고 왼쪽 또는 오른쪽 자식이 전달됩니다. 종이와 연필/펜으로 나무를 통과 해보십시오. 그러면 노드가 어떻게 추가되는지 알 수 있습니다.

Answer 2

귀하의 오해는 행동의 addNode입니다. 이 아닌 경우 새로 추가 된 노드에 대한 포인터를 반환합니다. 오히려, 전달 된 노드에 대한 포인터를 p (NULL이 아닌 이상) 리턴합니다.

처음 단어가 추가 될 때만 root == NULL이되므로 root은 그 시점부터 동일한 값을 가지며이 동일한 값을 계속 반복해서 할당 받게됩니다. 이것은 NULL 포인터로 표시되는 빈 나무를 다루는 우아한 방법입니다.

addNode의 각 재귀 호출에는 p에 대해 값이 있습니다. 이것이 지역 변수가 작동하는 방법입니다. 그들은 에 국부적으로 특정한 기능의 전체 호출이 아닌을 호출합니다. 아마도 이것은 함수의 동작에 대한 오해를 불러 일으켰습니다.