char w[10]; // любая информационная часть элемента
struct node *childs; // указатель на дочерние узлы
int N; // количество дочерних узлов
};
1.6 Реализация бинарных деревьев
Рассмотрим задачу определения числа появления всех слов в некотором файле. Список слов заранее неизвестен. Слова будем запоминать в бинарном дереве. Используем рекурсивный алгоритм для работы с деревом.
struct node{
char word[20];
int count;
node *left, *right;
};
#define node* T;
T tree(T, char*);
void main()
{
node *root;
char word[20];
root = NULL;
while(getword(word) != EOF)
root = tree(root, word);
treeprint(root);
}
T tree(T p, char *w)
{
int cond;
if(p==NULL)//новое слово
{
p=(T)malloc(sizeof(node));
//проверка
strcpy(p->word, 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 = tree(p->left, w);
else //правое дерево
p->right – tree(p->right, w);
return p;
}
//--------------------
void treeprint(T p)
{
if(p != NULL)
{
treeprint(p->left);
print(%4d %s \n”, p->count, p->word);
treeprint(p->right);
}
}
1.7 Алгоритм пирамиды (метод Уильямса-Флойда)
Метод сортировки массива, предложенный и развитый Вильямсом и Флойдом, носит название алгоритма "пирамиды". Он основан на специальном представлении массива в форме бинарного дерева, обладающего особыми свойствами и называемого "пирамидой". Алгоритм имеет гарантированную трудоемкость вида 0(n log n) и не требует дополнительной памяти.
Высокая эффективность алгоритма и гарантированная надежность для самого "худшего" случая часто оказываются решающими факторами, заставляющими отдавать предпочтение этому способу сортировки.
Процесс сортировки состоит из двух этапов. На первом этапе массив преобразуется к виду "пирамиды".
На втором этапе осуществляется сортировка "пирамиды".
Под структурой бинарного дерева понимается множество элементов, обладающих иерархией следующего вида:
А[1]
А[2] А[3]
А[4] А[5] А[6] А[7]
А[8] А[9]...
Структура дерева имеет логический характер - в памяти компьютера все элементы массива все равно расположены последовательно. Каждый элемент в структуре бинарного дерева имеет два элемента-потомка A[2i] и A[2i+1], где i - индекс данного элемента ("предка"). Элементы массива, являющегося "пирамидой", обладают следующими дополнительными свойствами:
1. Любой элемент пирамиды A[i] не меньше, чем его элементы-потомки A[2i] и A[2i+1] (соответственно первый элемент обладает максимальным значением):
A[i]>=A[2i],
A[i] >= A[2i+1]
2. Любая подпоследовательность элементов вида А[n\2+1], А[n\2+2], ... А[n] также является пирамидой, обладающей свойствами 1 и 2.
После преобразования массива к форме пирамиды сортировка осуществляется следующим образом.
В массиве-пирамиде первый элемент не меньше остальных. Обменяем его с последним элементом и "укоротим" массив на 1 элемент с "хвоста". Наибольший элемент массива окажется последним.
"Укороченная" последовательность элементов может уже не быть пирамидой. Поэтому рассмотрим элемент А[1] и его потомки - А[2| и А[3]. Если элемент не меньше потомков, то последовательность является пирамидой. В противном случае меняем местами элемент А[1] и наибольший из потомков: mах( А[2], А[3]). Для элемента-потомка, который обменялся значением, повторяется процесс сравнения и обмена с потомками до тех пор пока последовательность не станет пирамидой. После циклического повторения описанного этапа сортировки пирамида станет отсортированным массивом.
{- Метод "пирамиды" (алгоритм Вильямса-Флойда)----------- }
procedure PIR;
var t, k, i: integer;
begin
for i : = 2 to n do { создание структуры бинарного дерева-"пирамиды" }
begin
t:=i;
while t <>1 do
begin
k := t div 2;
if a[k] >= a[t] then
t := 1
else
begin
OBMEN(a[k],a[t]);t :=k
end
end
end;
for i :=n-l downto 1 do { сортировка массива-"пирамиды"}
1.7 Алгоритм пирамиды (метод Уильямса-Флойда)