АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. II. Вивчення нового матеріалу.
  2. II. Вивчення нового матеріалу.
  3. II. Вивчення нового матеріалу.
  4. II. Вивчення нового матеріалу.
  5. II. Вивчення нового матеріалу.
  6. II. Вивчення нового матеріалу.
  7. II. Вивчення нового матеріалу.
  8. II. Вивчення нового матеріалу.
  9. II. Вивчення нового матеріалу.
  10. II. Вивчення нового матеріалу.
  11. RS-триггеры на логических элементах
  12. А) Оценка уровня подготовленности нового работника.

Для того чтобы вставить новый элемент в дерево, необходимо найти для него место. Для этого, начиная с корня, сравниваем значения узлов (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);

¼


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)