Деревья. При решении многих задач математики используется понятие графа

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

Связанный граф, в котором нет циклов, называется деревом. Рекурсивное определение дерева выглядит следующим образом: дерево либо пусто, либо состоит из элемента, содержащего указатели на непересекаю­щиеся деревья, называемые поддеревьями. Элементы, в которые не входит никаких ветвей, называются корневыми. Элементы, из которых не выходят ветви, называются листьями. То, что для списка принято называть элементом, для дерева часто называют узлом.

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

1) имеется только одна вершина, в которую не входит ни одного ребра (эта вершина называется корнем двоичного дерева);

2) в каждую вершину, кроме корня, входит одно ребро;

3) из каждой вершины (включая корень) исходит не более двух ребер.

При решении многих прикладных задач бывает удобно представлять наборы объектов в виде двоичных деревьев. Каждый элемент дерева имеет одного левого и одного правого последователя.

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

Существует три способа просмотра всех элементов двоичного дерева:

1) прямой просмотр – элемент; левая ветвь; правая ветвь;

2) обратный просмотр – левая ветвь; элемент; правая ветвь;

3) концевой просмотр – левая ветвь; правая ветвь; элемент.

Принципы объектно-ориентированного программирования

Объектно-ориентированный язык программирования характеризуется тремя основными свойствами:

Инкапсуляция – объединение в одном объекте данных и методов их обработки.

Наследование – создание новых объектов на базе ранее определенных. Новые объекты–потомки сохраняют свойства своих родителей и обладают специфическими свойствами.

Полиморфизм – возможность замещения методов объекта-родителя одноименными методами объекта-потомка.

Преимущества ООП в полной мере проявляются при разработке достаточно сложных программ. Инкапсуляция придает объектам совершенно особое свойство “самостоятельности”, максимальной независимости от остальных частей программы. Правильно сконструированный объект располагает всеми необходимыми данными и процедурами их обработки, чтобы успешно реализовать требуемые от него действия. Попытки использовать ООП для программирования несложных алгоритмических действий выглядят искусственными нагромождениями ненужных языковых конструкций.