Implementación del árbol binario en la pregunta C como se encuentra en K & R

Question

He estado leyendo el libro K & RC y tengo una pregunta .. en el 6to Capítulo sobre estructuras en la página 140-141, hay un código que se parece a esto (saqué algunas de las partes más irrelevantes)

/* 
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; 
} 

Y mi vergüenza está en la función main() en la raíz = addNode (raíz, palabra)

Si addNode devuelve un puntero a la recién agregado nodo (o al nodo en el que está la palabra si ya está en el árbol), ¿no "perdería" todos los datos sobre el árbol? ¿No debería quedarse como la raíz del árbol?

Gracias!

Answer 1

root siempre permanece como raíz del árbol. root se pasa como el primer parámetro de addNode que solo será malloc si es NULL, es decir, cuando se pasa root por primera vez. En llamadas posteriores, no cambiará root, solo modificará count, left o right. Tenga en cuenta que en recursivas llamadas addNodep no se pasa, sino que se pasa el elemento secundario izquierdo o derecho. Intenta atravesar el árbol con un papel, un lápiz o un bolígrafo y te darás cuenta de cómo se están agregando los nodos.

Answer 2

Su malentendido está en el comportamiento de addNode. Hace no devuelve un puntero al nodo recién agregado; más bien, devuelve un puntero al nodo que se pasó, p (a menos que fuera NULL).

Dado que el único momento en que root == NULL es cuando se agrega la primera palabra, root tendrá el mismo valor desde ese momento y se le asignará este mismo valor una y otra vez. Esta es solo una forma elegante de tratar con árboles vacíos, que están representados por el puntero NULL.

Recuerde que cada llamada recursiva de addNode tiene un valor diferente para p, sin embargo. Así es como funcionan las variables locales; son locales a una invocación particular de la función, no a la función como un todo. Tal vez esto condujo a su incomprensión del comportamiento de la función.