所以我一直在阅读 K&R C 书并有一个问题.. 在第 6 章关于结构的第 140-141 页,有一段代码看起来像这样(我去掉了一些更不相关的部分)
/*
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;
}
我的困惑在于 root = addNode(root, word) 的 main() 函数
如果 addNode 返回指向新添加的节点的指针(或者如果单词已经在树中,则返回指向该单词所在的节点),这不会“丢失”树上方的所有数据吗? root 不应该作为树的根吗?
谢谢!
最佳答案
root
始终作为树的根。 root
作为 addNode
的第一个参数传递,如果它是 NULL
,它只会 malloc
,即当 root
是第一次通过。在以后的调用中,它不会更改 root
,只会修改 count
、left
或 right
。请注意,在递归 addNode
调用中,p
不会被传递,而是它的左子节点或右子节点被传递。尝试用纸和铅笔/笔遍历树,您将了解如何添加节点。
关于c - K&R 中发现的 C 问题中的二叉树实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6561644/