Лабораторная работа № 20
Тема: «Обработка динамических структур данных»
Рассмотрим работу с бинарным деревом (в котором у каждого узла может быть только два приемника - левый и правый сын). Необходимо уметь:
построить дерево;
выполнить поиск элемента с указанным значением в узле;
удалить заданный элемент;
обойти все элементы дерева (например, чтобы над каждым из них провести некоторую операцию).
Обычно бинарное дерево строится сразу упорядоченным, т.е. узел левого сына имеет значение меньшее, чем значение родителя, а узел правого сына - большее. Например, если приходят числа 17, 18, 6, 5, 9, 23, 12, 7, 8, то построенное по ним дерево будет выглядеть так (рис. 15.6).
Для того, чтобы вставить новый элемент в дерево, надо найти для него место. Для этого, начиная с корня, будем сравнивать значения узлов (Y) со значением нового элемента (NEW). Если NEW < Y, то пойдем по левой ветви; в противном случае - по правой. Когда дойдем до узла, из которого не выходит нужная ветвь для дальнейшего поиска, это означает, что место под новый элемент найдено.
Путь поиска места для числа 11 в построенном выше дереве показан на рис. 15.7.
При удалении узла из дерева возможны три ситуации:
а) исключаемый узел - лист (в этом случае надо просто удалить ссылку на данный узел);
б) из исключаемого узла выходит только одна ветвь;
в) из исключаемого узла выходят две ветви (в таком случае на место удаляемого узла надо поставить либо самый правый узел левой ветви, либо самый левый узел правой ветви для сохранения упорядоченности дерева). Например, построенное ранее дерево после удаления узла 6 может стать таким (рис. 15.8).
Рассмотрим задачу обхода дерева. Существуют три способа обхода, которые естественно следуют из самой структуры дерева.
Обход слева направо: A, R, В (сначала посещаем левое поддерево, затем - корень и, наконец, правое поддерево).
Обход сверху вниз: R, А, В (посещаем корень до поддеревьев).
Обход снизу вверх: А, В, R (посещаем корень после поддеревьев).
Интересно проследить результаты этих трех обходов на примере записи формул в виде дерева.
Например, формула
(а+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) ; )