K＆Rで見つけたC質問のバイナリツリーの実装

Question

私はK & RCの本を読んできました。質問があります。140-141ページの第6章のstructsに、このようなコードがありますaddNodeが新しく追加されたへのポインタを返す場合

を

/* 
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（根、単語）で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の異なるの値があることに注意してください。これはローカル変数の仕組みです。彼らはのローカルなので、関数の全体ではなく、関数の特定の呼び出しです。多分このことが、関数の振る舞いを誤解させたのかもしれません。