Язык программирования Си
Память для нового узла запрашивается
/* addtree: добавляет узел со словом w в р или ниже него */ struct tnode *addtree(struct tnode *p, char *w) { int cond;
if (р == NULL) { /* слово встречается впервые */ p = talloc(); /* создается новый узел */ 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 = addtree(p->left, w); else /* больше корня правого поддерева */ p->right = addtree(p->right, w); return p; }
Память для нового узла запрашивается с помощью программы talloc, которая возвращает указатель на свободное пространство, достаточное для хранения одного узла дерева, а копирование нового слова в отдельное место памяти осуществляется с помощью strdup. (Мы рассмотрим эти программы чуть позже.) В тот (и только в тот) момент, когда к дереву подвешивается новый узел, происходит инициализация счетчика и обнуление указателей на сыновей. Мы опустили (что неразумно) контроль ошибок, который должен выполняться при получении значений от strdup и talloc.
Функция treeprint печатает дерево в лексикографическом порядке: для каждого узла она печатает его левое поддерево (все слова, которые меньше слова данного узла), затем само слово и, наконец, правое поддерево (слова, которые больше слова данного узла).
/* treeprint: упорядоченная печать дерева р */ void treeprint(struct tnode *p) { if (p != NULL) { treeprint (p->left); printf("%4d %s\n", p->count, p->word); treeprint(p->right); } }
Если вы не уверены, что досконально разобрались в том, как работает рекурсия, "проиграйте" действия treeprint на дереве, приведенном выше. Практическое замечание: если дерево "несбалансировано" (что бывает, когда слова поступают не в случайном порядке), то время работы программы может сильно возрасти. Худший вариант, когда слова уже упорядочены; в этом случае затраты на вычисления будут такими же, как при линейном поиске. Существуют обобщения бинарного дерева, которые не страдают этим недостатком, но здесь мы их не описываем.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий