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

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

будет представлена след. образом

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

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

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

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

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

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

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

#include<stdio.h>

#include<conio.h>

#include<string.h>

#include<windows.h>

char buf[256];

char *rus(char *text)

{CharToOem(text,buf);

return buf;}

struct info

{ char *w;

int c;

};

struct TREE

{ info d;

TREE *l;

TREE *r;

};

TREE *first(char *word);//фармирование первого элемента дерева

TREE *der(TREE *kr, char *word);//добавление элемента

void print_der(TREE *kr);//просмотр элементов дерева

void main()

{ int i=0;

char word[40][20],ch;

puts(rus("Введите фамилии, пока не нажата клава Esc"));

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

TREE *kr=first(word[i]);

do

{

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

der(kr,word[i]);

printf("");}

while((ch=getch())!=27);

print_der(kr) ;

}

TREE *first(char *word)

{TREE *pv=new TREE;

(pv->d).w=word;

(pv->d).c=1;

pv->l=0;

pv->r=0;

return pv;}

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

{TREE *pv=kr,*prev;

int flag=0;

int sr;

while(pv&&!flag)

{prev=pv;

if((sr=strcmp(word, (pv->d).w))==0) {((pv->d).c)++;flag=1;}

else if(sr<0) pv= pv->l;

else pv= pv->r;}

if (flag) return pv;

// Создание нового узла

TREE *pnew=new TREE;

(pnew->d).w=word;

(pnew->d).c=1;

pnew->l=0;

pnew->r=0;

if(sr<0) prev->l= pnew;

else prev->r=pnew;

return pnew;

}

void print_der(TREE *kr)

{

if(kr)

{ print_der(kr->l);

printf(rus("Фамилия - %-20s \tКол-во повторов.- %d\n"), (kr->d).w, (kr->d).c);

print_der (kr->r) ;

}

}