![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Для того чтобы вставить новый элемент в дерево, необходимо найти для него место. Для этого, начиная с корня, сравниваем значения узлов (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);
¼
Дата публикования: 2015-09-17; Прочитано: 213 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!