Основы программирования для автоматизированного проектирования и решения творческих задач. Романенко А.В - 31 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

scanf("%d", &key);
if (first == NULL)
first = (struct Tree *) malloc(sizeof(struct Tree)),
first->left = first->right = NULL,
first->key = key;
else
{
int i = 1;
tree = first;
while (i)
{
if (key < tree->key)
{
if (tree->left != NULL)
tree = tree->left;
else
tree->left = (struct Tree *)
malloc(sizeof(struct Tree)),
tree = tree->left,
i = 0;
}
else
{
if (tree->right != NULL)
tree = tree->right;
else
tree->right = (struct Tree *) malloc(sizeof(struct Tree)),
tree = tree->right,
i = 0;
}
}
tree->left = tree->right = NULL;
tree->key = key;
}
Удаление элементов бинарного дерева. Эта процедура сопряжена с некоторыми трудностями, вызванными необходимо-
стью обеспечения целостности дерева в процессе проведения операции.
Если удаляемый элемент является конечным элементом дерева (не имеет ни левой, ни правой ветвей), то он удаляется
обычным образом. При этом соответствующему указателю элемента, в ветви которого находится удаляемый элемент, нужно
присвоить NULL, так как эта ветвь удаляется.
Если удаляемая вершина имеет одну ветвь продолжения, то необходимо передать указателю верхнего элемента адрес
этой ветви, после чего сам элемент можно удалить.
При удалении вершины, имеющей две ветви, главную трудность составляет то, что на удаляемую вершину указывает
один элемент. Поступают в этом случае следующим образом: на место удаляемой вершины перемещают подходящий эле-
мент, который сохранит принцип организации дерева в целом. Таким звеном является либо самый правый элемент в левой
ветви, либо самый левый элемент в правой ветви относительно удаляемого элемента. Его содержимое переписывают в ячей-
ку с удаляемой информацией, а сам элемент после этого удаляют.
Поиск информации в бинарном дереве осуществляется аналогично процедуре добавления нового элемента. Отличие со-
стоит в том, что нужно найти элемент, у которого ключевое поле совпадает со значением ключа поиска.
13 РАБОТА С ФУНКЦИЯМИ В ЯЗЫКЕ С
13.1 Описание и порядок исполнения функций
Понятие функции является для языка программирования С ключевым, так как в основе языка лежат принципы модуль-
ного программирования. Функция представляет собой обособленный фрагмент текста программы, предназначенный для вы-
полнения определенных действий и, часто, возвращающий некоторый результат.
Каждая программа на языке С должна содержать единственную главную функцию с именем main, которая обеспечива-
ет начало работы откомпилированной программы. Помимо нее программа может содержать неограниченное число других
функций, вызов на исполнение которых осуществляется функцией main. Каждая функция в программе должна иметь уни-
кальное имя, по которому осуществляется обращение к ней. Всем именам функций по умолчанию присваивается класс па-
мяти extern, т.е. функции имеют внешний тип компоновки и статическую продолжительность существования. Для доступ-
ности в модуле функция должна быть определена в нем до первого вызова.
В определении функции указываются: последовательность выполняемых действий, имя функции, тип возвращаемого
значения и описания формальных параметров с указанием соответствующих типов данных. Определение функции разбива-
ют на две части – заголовок и тело функции:

Страницы