Например, формула

(а+b/с)*(d-e*f)

будет представлена так (рис. 15.9).

(дерево формируется по принципу: операция - узел, операнды - поддеревья).

Обход 1 даст обычную инфиксную запись выражения (правда, без скобок).

Обход 2 - префиксную запись *+а/bс-d*ef

Обход 3 - постфиксную (ПОЛИЗ - польская инверсная
запись): abc/+def*-*.

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

Вводятся фамилии абитуриентов; необходимо распечатать их в алфавитном порядке с указанием количества повторений каждой фамилии.

В программе будет использована рекурсивная функция der(), которая строит дерево фамилий, а также рекурсивная • функция для печати дерева print_der(), в которой реализован первый способ обхода дерева.

#include<alloc.h> #include<stdio.h> #define TREE struct der TREE

{ char *w; int с; TREE *l; TREE *r; };

TREE *der(TREE *kr, char *word) {

int sr; if(kr=NULL)

{

kr=(TREE *)malloc(sizeof(TREE)); kr->w=word; kr->c=l; kr->l=kr->r=NULL; }

else if((sr=strcrap(word, kr->w))=0) kr->c++;

else if<sr<0) Jcr->l = der(kr->l, word);

else kr->r = der(kr->r, word); return kr;)

void print_der(TREE *kr) <

if<kr) < print_der(kr->l);

printf("onoao - %-20s \tKon-BO повтор.- %d\n", kr->w, kr->c); print_der (kr->r);))

void main() < int i; TREE *kr;

static char word[40][21]; kr=NULL; i=0;

puts("BeeAMTe <40 фамилий длиной <20 каждая"); scanf <"%s", word[i]); while(word[i][0]!='\0')

{ kr=der(kr,word[H);

scanf("%s", word[++i]); }

print_der(kr);)