K&R 中 C 问题中的二叉树实现

Question

所以我一直在阅读 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;
}

和我的混乱在于 main() 函数中 root = addNode(root, word)

如果 addNode 返回指向新添加的节点的指针（或者如果 word 已经在树中，则返回指向 word 所在的节点），那不是吗“丢失”树上面的所有数据？根不应该作为树的根吗？

谢谢！

Answer 1

root 始终作为树的根。 root 作为 addNode 的第一个参数传递，如果为 NULL，即当 >root 是第一次传递。在以后的调用中，它不会更改 root，只会修改 count、left 或 right。请注意，在递归 addNode 调用中，不会传递 p，而是传递它的左或右子节点。尝试用纸和铅笔/钢笔浏览树，您将意识到节点是如何添加的。

Answer 2

您的误解在于 addNode 的行为。它不返回指向新添加节点的指针；相反，它返回一个指向传入的节点的指针，p（除非它是NULL）。

由于 root == NULL 唯一一次是在添加第一个单词时，因此 root 从那时起将具有相同的值，并被分配这个完全相同的值反复。这只是处理空树的一种优雅方式，空树由 NULL 指针表示。

请记住，addNode 的每个递归调用都有一个 p 的不同值。这就是局部变量的工作原理；它们是函数的特定调用的本地函数，而不是整个函数的本地函数。也许这导致您对该函数的行为产生误解。