Пример. Использование бинарного дерева для сортировки данных
Допустим дана последовательность чисел, например:
• 15 10 20 12 8 17 25 5 9
Вывести числа в порядке возрастания:
• 5 8 9 10 12 15 17 20 25
Построим бинарное дерево: первое число будет корнем дерева. Если второе число < 1-го, то оно станет корнем левого поддерева, а если > 1-го, то станет корнем правого поддерева. Каждое следующее число будет добавляться либо в левое поддерево, либо в правое.
Алгоритм:
1. Создание бинарного дерева в виде регулярной сети.
2. Обход дерева слева направо и вывод меток его вершин (чисел).
3. Удаление дерева (освобождение памяти).
Программа
#include <stdio.h>
#include <stdlib.h>
/* Описание бинарного дерева в виде регулярной сети */
// Тип вершины дерева (элемента сети)
struct TREE
{ float number; // число
struct TREE *left, *right; /* указатели на левое и правое поддеревья*/
};
// Прототипы функций
void insert (struct TREE *pt, float x);
void print_tree (struct TREE *pt);
void delete_tree (struct TREE *pt);
/*--------------------------------------*/
/* Главная функция */
/*--------------------------------------*/
void main()
{ struct TREE *pt; // указатель на корень дерева
float x; // очередное число
puts ("\nВведите числовую последовательность");
scanf("%f", &x);
// создание корня дерева
pt = (struct TREE *) malloc (sizeof(struct TREE));
pt->number=x;
pt->left=pt->right=NULL;
// ввод чисел и формирование дерева while (scanf("%f", &x) != EOF)
Цель:рассмотреть основные виды бинарных отношений (эквивалентность, отношение порядка, толерантность)
Бинарное отношение может иметь одновременно несколько свойств. Некоторые сочетания этих свойств определяют особенно интересные отношения, наиболее часто встречающиеся как на практике, так и в математических теориях.
1 Отношения эквивалентности
При поломке какой-нибудь детали автомобиля ее заменяют другим экземпляром той же детали. Различные экземпляры одной и той же детали неотличимы друг от друга; они, как говорят, эквивалентны (равноценны). Точно так же эквивалентны все монеты одного и того же достоинства и года выпуска, все костюмы одной и той же модели и размера, сделанные из одинакового материала, и т. д.
Не всегда эквивалентность сводится к простой одинаковости. Например, если требуется уплатить сумму в 1 руб., то бумажный и металлический рубли эквивалентны друг другу, равно как и 5 двадцатикопеечных монет, или 20 пятачков. В физике считаются эквивалентными взаимозаменяющие друг друга количества энергии (например, 1 ккал эквивалентна 4190 Дж и т.д.).
Выясним, какими общими свойствами обладает отношение взаимозаменяемости объектов. Во-первых, ясно, что каждый объект может сам себя заменить. Это значит, что для всех х должно выполняться отношение xRx, т. е. отношение взаимозаменяемости должно быть рефлексивным. Во-вторых, если х взаимозаменяемо с у, то и у взаимозаменяемо с х. Иными словами, если xRy, то и yRx, а потому R симметрично. Наконец, если х взаимозаменяемо с у, а у взаимозаменяемо с z, то х взаимозаменяемо с z. Иными словами, из xRy и yRz следует xRz, т. е. R транзитивно.
Итак, отношение взаимозаменяемости должно обладать свойствами рефлексивности, симметричности и транзитивности. Эти свойства характеризуют взаимозаменяемость, и потому мы вводим следующее определение:
Отношением эквивалентности в множестве X называется любое рефлексивное, симметричное и транзитивное отношение R.
Приведем примеры таких отношений.
Пример 1. Отношение равенства геометрических фигур рефлексивно (каждая фигура сама себе равна), симметрично (если фигура х равна фигуре у, то и фигура у равна фигуре х) и транзитивно (если фигура х равна фигуре у, а фигура у – фигуре z, то х и z равна). Значит, отношение равенства – эквивалентность в множестве геометрических фигур.
Пример 2. Отношение подобия геометрических фигур также является отношением эквивалентности.
Пример 3. Отношение параллельности прямых также обладает свойствами рефлексивности, симметричности и транзитивности, а потому является отношением эквивалентности в множестве прямых.
Пример 4. Отношение равносильности двух уравнений рефлексивно (каждое уравнение равносильно самому себе), симметрично (если одно уравнение равносильно другому, то и второе равносильно первому) и транзитивно. Значит, оно является эквивалентностью в множестве уравнений.
Пример 5. Отношение равенства дробей тоже является эквивалентностью. В самом деле, дроби и равны в том и только в том случае, когда ad = bс. Легко проверяется, что (наше равенство принимает вид: аb = аb) и что из = следует = (из ad = be следует cb = da). Докажем транзитивность этого отношения. Пусть = и = . Это значит, что ad = bc и сf = de. Но тогда adf = bcf и bcf = bde, а потому adf = bde. Отсюда получаем, что af = be, а это и значит = .
Отношение «жить в одном доме» является эквивалентностью в множестве людей (оно рефлексивно, симметрично и транзитивно), а отношение «жить на одной улице» эквивалентностью не является. Дело в том, что человек у может жить в угловом доме на пересечении двух улиц, а х и z – на этих улицах. Тогда х и у живут на одной улице, равно как у и z, но х и z живут на разных улицах. Не является эквивалентностью и отношение «служить в одном полку» в множестве военнослужащих. Оно симметрично и транзитивно, но не рефлексивно – есть военнослужащие, не принадлежащие никакому полку (например, моряки), и о них нельзя сказать, что они служат в одном полку сами с собой.
Множество всех учащихся данной школы разбито на классы 1А, 1Б, ..., 10Б. С этим разбиением связано отношение «учиться в одном классе», являющееся эквивалентностью.
Непересекающиеся множества, на которые разбивается множество М отношением эквивалентности, называются классами эквивалентности. Другими словами, классом эквивалентности, порожденным элементом х, называется множество всех элементов из М, вступающих с х в отношение эквивалентности. Множество всех различных классов эквивалентности называется фактор-множеством множества М по отношению к эквивалентности R и обозначается М \ R. Например, множество всех рациональных чисел Q можно разбить на классы эквивалентности, для которых – рациональная дробь, где
Разбиение множества на попарно непересекающиеся подмножества лежит в основе всех классификаций. Например, в библиотеках множество всех книг разбивают на книги по математике, по физике, по химии, по истории и т. д., в биологии множество всех живых существ разбивают на виды, множество видов – на роды и т. д.
и 
равны в том и только в том случае, когда ad = bс. Легко проверяется, что 
(наше равенство принимает вид: аb = аb) и что из 
. Это значит, что ad = bc и сf = de. Но тогда adf = bcf и bcf = bde, а потому adf = bde. Отсюда получаем, что af = be, а это и значит 