Функция обхода дерева снизу вверх

Функция обхода дерева слева направо

void { i {	postorder (struct node	*t)
f(t!=NULL)
postorder (t->left);
	postorder (t->right);
} }	P(t);

void { i {	inorder (struct node	*t)
f (t!=NULL)
inorder (t->left);
	P(t);
} }	inorder (t->right);

Здесь Р — операция, которую надо выполнить с узлом; t — указатель на дерево.

В заключение рассмотрим пример [7]. Необходимо написать программу, подсчитывающую частоту встречаемости для любых слов входного потока. Поскольку список слов заранее не известен, мы не можем предварительно упорядочить его и применить бинарный поиск. Было бы неразумно пользоваться и линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет. В этом случае программа работает слишком медленно.

Как можно организовать данные, чтобы эффективно справиться со списком произвольных слов?

Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Воспользуемся структурой данных, называемой бинарным деревом.

В дереве на каждое отдельное слово предусмотрим узел, который содержит:

1) указатель на текст слова;

2) счетчик числа встречаемости;

3) указатель на левого потомка;

4) указатель на правого потомка.

У каждого узла может быть один или два сына, или узел может вообще не иметь сыновей.

Узлы в дереве располагаются так, что по отношению к любому узлу левое поддерево содержит только те слова, которые лексикографически меньше, чем слово данного узла, а правое — слова, которое больше него. Вот как выглядит дерево, построенное для фразы «now is the time for all good men to come to the aid of their party» (настало время всем добрым людям помочь своей партии), после завершения процесса (рис. 2.18).

now
is	^the
/ \	/	\
for men	of	time
/\	\	/	\
all good	party their	to
/\
aid come

Рис. 2.18. Дерево

Чтобы определить, помещено ли в дерево новое слово, начинают с корня, сравнивая слева со словом из корневого узла. Если совпали, ответ положительный. Если новое слово меньше слова из дерева, то поиск продолжается в левом поддереве, если больше, то в правом. Если же в выбранном направлении поддерева нет, то этого слова в дереве нет, а пустующая ссылка — место, куда помещается новое слово. Описанный процесс — рекурсивен, поэтому применяем рекурсивные функции.О

Описание узла

struct tnode { char *word;
		/^указатель на строку*/
int count;			/*число вхождений*/
struct tnode	*le	ft;	/*левый потомок*/
struct tnode };	*ri	ght;	/*правый потомок*/

Главная программа main читает слова с помощью getword и вставляет их в дерево посредством addtree.

Функция addtree рекурсивна. Первое слово функция main помещает в корень дерева. Каждое новое слово сравнивается со словом узла и погружается в левое или правое поддерево. При совпадении слова с каким-либо словом дерева к счетчику count добавляется 1, в противном случае создается новый узел.

Память для нового узла запрашивается программой talloc, которая возвращает указатель на свободное пространство; копирование нового слова осуществляет функция strdup. В программе для простоты опущен контроль ошибок.

Функция treeprint печатает дерево в лексикографическом порядке. Для каждого узла вначале печатается левое поддерево, затем узел, затем правое поддерево.

Функция talloc распределяет память.

Функция strdup копирует строку, указанную в аргументе, в место, полученное с помощью malloc.

Функция getword принимает следующее слово или литеру из ввода. Она обращается к getch и ungetch. После окончания набора букв-цифр оказывается, что getword взяла лишнюю литеру. Она возвращается функцией ungetch назад во входной поток.

В getword используются следующие функции: 1) isspace — пропуск пробельных литер; 2) isalpha — идентификация букв; 3) isalnum — идентификация букв-цифр.

Функции getch и ungetch совместно используют буфер и индекс, значения которых должны сохраняться между вызовами, поэтому они должны быть внешними.

Функция ungetch возвращает одну литеру.

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#define MAXWORD 100
#define BUFSIZE 100
struct tnode {	/*	узел дерева: */
char *word;	/*	указатель на строку */
int count;	/*	число вхождений */
struct tnode *left;	/*	левый потомок*/
struct tnode *right; };	/*	правый потомок */

struct tnode *addtree(st	ruct	tnode *, с	^har *);
struct tnode *talloc(voi	d);
void treeprint(struct tnode *	);
void ungetch(int);
int getword(char *, int)	r
int getch(void);
char buf[BUFSIZE];	/*	буфер для	ungetch */
int bufp = 0;	/*	следующая	свободная */
	/*	позиция в	буфере */
int main(void) {	/*	ввод строки символов */
struct tnode *root;
char word[MAXWORD];
root = NULL;
while(getword(word, MAXWORD)	!= EOF)
if(isalpha(word[0]))
root = addtree(root,	word);
treeprint(root);
exit(0); }
/* Функция getword() получает	^п следующее слово из входного
потока. */
int getword(char *word,	int 1	-im) {
int c, getch(void);
void ungetch(int);
char *w = word;
while(isspace(c = getch()))
r if(c!= EOF)
*w++ = c;
if(!isalpha(c)) {
*w = 'Non-
return c; } for(; --lim > 0; w++)
if(!isalnum(*w = getch()))	{
ungetch(*w);
break; } *w = 'Non-
return word[0]; }

/* Функция addtree() добавляет узел к дереву.*/ struct tnode *addtree(struct tnode *p, char *w) { int cond; if(p == 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() выделяет память под узел. */ struct tnode *talloc(void) { return(struct tnode *)malloc(sizeof(struct tnode));

}

/* Функция treeprint () печатает дерево. */ void treeprint(struct tnode *p) { if(p!= NULL) { treeprint(p->left);

printf("%4d %s\n", p->count, p->word); treeprint(p->right); } }

int getch(void) {

return (bufp > 0)? buf[--bufp]: getchar(); }

void ungetch(int c) { if(bufp >= BUFSIZE)

printf("ungetch: слишком много символов\п"); else

buf[bufp++] = с;

}

Глава 3. Сортировка и поиск

Дата добавления: 2014-11-29