Вставка нового элемента

Для того чтобы вставить новый элемент в дерево, необходимо найти для него место. Для этого, начиная с корня, сравниваем значения узлов (Tree->info) со значением нового элемента (b). Если b < info, то идем по левой ветви, в противном случае – по правой ветви. Когда дойдем до узла, из которого не выходит нужная ветвь для дальнейшего поиска, это означает, что место под новый элемент найдено.

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

Функция создания дерева, ключами которого являются целые положительные числа, может иметь следующий вид:

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);

¼

Поиск по сайту: