Реализация двоичного дерева в вопросе C, найденная в K&R

Итак, я читал книгу 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;
}

И меня смущает функция main() в root = addNode(root, word)

Если addNode возвращает указатель на только что добавленный узел (или на узел, в котором находится слово, если оно уже находится в дереве), не «потеряет» ли это все данные над деревом? Разве root не должен оставаться корнем дерева?

Спасибо!


c tree binary-search-tree kernighan-and-ritchie
person adelbertc    schedule 03.07.2011    source источник
comment
Я немного описал рекурсию здесь: stackoverflow.com/questions/6420309/   -  person stacker    schedule 03.07.2011

Ответы (2)


arrow_upward
5
arrow_downward

root всегда остается корнем дерева. root передается как первый параметр addNode, который будет только malloc, если это NULL, т.е. когда root передается в первый раз. В более поздних вызовах он не изменит root, изменит только count, left или right. Обратите внимание, что в рекурсивных вызовах addNode p не передается, а передается левый или правый дочерний элемент. Попробуйте пройтись по дереву с бумагой и карандашом/ручкой, и вы поймете, как добавляются узлы.

person taskinoor    schedule 03.07.2011

arrow_upward
3
arrow_downward

Ваше непонимание заключается в поведении addNode. Он не возвращает указатель на вновь добавленный узел; скорее, он возвращает указатель на переданный узел p (если только это не NULL).

Поскольку единственный раз, когда root == NULL добавляется самое первое слово, root с этого момента будет иметь одно и то же значение, и ему снова и снова будет присваиваться одно и то же значение. Это просто элегантный способ работы с пустыми деревьями, которые представлены указателем NULL.

Помните, что каждый рекурсивный вызов addNode имеет различное значение для p. Вот как работают локальные переменные; они локальны для конкретного вызова функции, а не для функции в целом. Возможно, это привело к вашему непониманию поведения функции.

person Thomas    schedule 03.07.2011