Алгоритмизации
 Скачать 1.15 Mb.
|
ВставкановогоэлементаДля того чтобы вставить новый элемент в дерево, необходимо найти для него место. Для этого, начиная с корня, сравниваем значения узлов (Tree->info) со значением нового элемента (b). Еслиb < info, то идем по левой ветви, в противном случае – по правой ветви. Когда дойдем до узла, из которого не выходит нужная ветвь для дальнейшего поиска, это означает, что место под новый элемент найдено. Путь поиска места в построенном дереве для числа 11:  11<17 176 11>6 9 5 18 23 11>9 7 12 8 11 11< 12 и из узла (12) нет ветви Функция создания дерева, ключами которого являются целые положительные числа, может иметь следующий вид: Tree* Make(Tree *Root) { Tree *Prev, *t; // Prevродитель (предыдущий) текущего элемента int b, find; if ( Root == NULL ) { // Если дерево не создано printf("\n Input Root : "); scanf(“%d”, &b); Root = List(b); // Установили указатель на корень } //================ Добавление элементов ================= while(1) { printf("\n Input Info : "); scanf(“%d”, &b); if (b<0) break; // Признак выхода число < 0 t = Root; // Текущий указатель на корень find = 0; // Признак поиска while ( t && ! find) { Prev = t; if( b == t->info) find = 1; // Ключи должны быть уникальны else } if ( b < t -> info ) t = t -> Left; else t = t -> Right; if (!find) { // Нашли место с адресом Prev t = List(b); // Создаем новый узел if ( b < Prev -> info ) // и присоединяем его, либо Prev -> Left = t; // на левую ветвь, else Prev -> Right = t; // либо на правую ветвь } } // Конец цикла return Root; } Функция Listпредназначена для создания нового элемента – листа: Tree* List(int i) { Tree *t = (Tree*) malloc (sizeof(Tree)); t -> info = i; t -> Left = t -> Right = NULL; return t; } Участок кода с обращением к функции Createбудет иметь следующий вид: … struct Tree { // Декларация шаблона int info; Tree *Left, *Right; }; void main() { Tree *Root = NULL; // Указатель корня … Root = Make(Root); … |