Упорядоченное двоичное дерево и его свойства

Упорядоченным называется такое дерево, в котором упорядочены все потомки каждой вершины. Принято считать, что на диаграмме деревья изображаются так, чтобы все потомки были упорядочены слева направо. Двоичное (бинарное) дерево можно определить как упорядоченное дерево, каждая вершина которого имеет не более двух потомков, причем каждый из потомков считается либо левым, либо правым потомком своего родителя. Поддерево, корень которого находится в левом (правом) потомке вершины, называется левым (правым) поддеревом этой вершины.

Двоичное дерево упорядоченно, если для любой его вершины x справедливы такие свойства:

1) все элементы в левом поддереве меньше элемента, хранимого в x;

2) все элементы в правом поддереве больше элемента, хранимого в x;

3) все элементы дерева различны.

Пример упорядоченного двоичного дерева представлен на рисунке 3:

Рисунок 3 – Упорядоченное двоичное дерево

Если в дереве выполняются первые два свойства, но встречаются одинаковые элементы, то такое дерево является частично упорядоченным. Основными операциями, производимыми с упорядоченным деревом, являются:

1) поиск вершины;

2) добавление вершины;

3) удаление вершины;

4) вывод (печать) дерева;

5) очистка дерева.

Распишите как выполняются все перечисленные выше операции. при этом более подробно остановитесь на добавлении вершин. Словесное описание снабдите рисунками.

Словесная постановка задачи

Написать программу на языке высокого уровня C, позволяющую строить упорядоченное двоичное дерево. В программе должны быть реализованы функции:

1) поиска вершины;

2) добавление вершины;

3) вывод (печать) дерева;

4) очистка дерева.

При реализации дерева использовать списки.

Требования к программе:

1) текст программы должен сопровождаться комментариями;

2) в заголовке указать имя автора, группу, краткую формулировку задания – эта же информация должна выводиться на экран при запуске программы;

3) переменные должны иметь осмысленные имена, при этом желательно объявление переменной снабжать комментарием о ее назначении;

4) следует структурировать программу, разбивая ее на (относительно) независимые части;

5) длинные программы (свыше 200 строк) следует разбивать на несколько файлов, и создавать проект;

6) интерфейс программы должен быть достаточно удобен для пользователя: пользователю должна предоставлять возможность выбора действия (поиска, добавления элемента или вывода дерева);

7) программа должна компилироваться без ошибок и предупреждений при всех включенных сообщениях компилятора;

8) исходные данные должны вводиться с клавиатуры или из файла;

9) реализовать графический интерфейс.

Проектный раздел

Математическая постановка задачи

Здесь нужно выполнить мат постановку вашей задачи

Алгоритм решения задачи