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

Question

所以我一直在阅读K&R C书,并在第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返回一个指向新添加的节点的指针(或者指向该单词所在的节点,如果它已经在树中),那么不会"丢失"树上方的所有数据吗？不应该留根作为树的根？

谢谢!

Answer 1

root总是留在树的根部.root作为第一个参数传递,addNode只有malloc当它是NULL,即root第一次传递时.在以后的调用中它不会改变root,只会修改count,left或right.请注意,在递归addNode调用p中不会传递,而是传递左或右子节点.尝试用纸和铅笔/钢笔穿过树,你会发现如何添加节点.