Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
СТВОРЕННЯ I ВЕДЕННЯ БІНАРНИХ ДЕРЕВ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми і структури даних
Група:
КН-24
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР
Лабораторна робота №3
СТВОРЕННЯ I ВЕДЕННЯ БІНАРНИХ ДЕРЕВ
з курсу: “Алгоритми и структури данних”
Виконав студент
групи КН – 24
Прийняв
ЛЬВІВ 2007
Мета роботи
Ознайомитися iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi бінарних дерев. Оволодiти методами роботи iз бінарними деревами.
Теоретичні відомості
Для описання будь-якої структури, яка характеризується ієрархiчними зв'язками, є корисними дерева.
Існує два типи схем, що використовуються у дослідженнях генеалогії. Перший тип називається схемою родоводу, другий - схемою нащадків.
Якими б не були дерева, усі вони мають набір спільних властивостей. У кожному дереві є визначений вузол - корінь. Вузол, у якого немає нащадків, називається термінальним вузлом, або листом. Всі інші вузли називаються гілковими вузлами.
Дерево - це визначена множина одного чи кількох вузлів, таких, що:
Є спеціально визначений вузол, що називається коренем.
Інші вузли є розділениними на підмножини, що не перетинаються Т1, Т2, Т3,..., Тn (n>=0), кожна з яких є деревом. Кожне Ті(1<=i<=n) називається піддеревом вузла.
Рівнем вузла є 1 плюс довжина шляху до нього від кореня.
Степенем вузла є кількість піддерев, які з нього виходять.
Впорядкованим називається дерево, у якого вузли на кожному рівні впорядковані певним чином.
Якщо видалити корінь із гілками, то отримується множина незв'язаних дерев. Кожен набір незв'язаних дерев називається лісом.
Якщо степінь кожного вузла є меншим або дорiвнює 2, то дерево називається бінарним.
Бінарним деревом називається множина m (m>=0) вузлів, що є або порожньою (m=0), або містить кореневий вузол, який має два незв'язаних бінарних піддерева, що називається лівим піддеревом і правим піддеревом.
Бінарне дерево, у якого кожний вузол має степінь 0 чи 2, називається повністю бінарним деревом.
Оскільки бінарні дерева легко зображати і маніпулювати з ними, зручно перетворити будь-яке дерево в еквівалентну бінарну форму (якщо можливо).
Індивідуальне завдання
Реалізувати бінарне дерево.
Текст програми:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
//-----DATA SRUCTURES----------
typedef char type_of_element;
struct unit
{
type_of_element key;
unit * left;
unit * right;
unit * parent;
};
//----------------------------
void tree_insert(unit **, type_of_element);
void inorder_tree_walk(unit *);
unit * tree_search(unit *, type_of_element);
unit * initialization_tree(void);
unit * tree_minimum (unit *);
unit * tree_successor(unit *);
unit * tree_delete(unit *, unit *);
//--------MAIN---------------
void main (void)
{
unit * root;
root=initialization_tree();
type_of_element element;
while (1)
{
printf ("\n 1 - add element\n2 - delete element\n 3 - show tree \n4 - exit \n");
int answer;
scanf(" %d",&answer);
switch (answer)
{
case 1:{ printf("\n Enter the key of current element\n");
scanf(" %c",&element);
tree_insert(&root,element);
}; break;
case 2:{ type_of_element symbol;
printf("\n Enter the key of element \n");
scanf(" %c",&symbol);
tree_delete(root, tree_search(root, symbol));
}; break;
case 3:{ inorder_tree_walk(root); }; break;
default:{ printf("\n Good bye \n"); goto l1; }
}
}
l1: getch();
}
//----INSERTING FUNCTION-------------
void tree_insert(unit ** root, type_of_element element)
{
unit * run_pointer,* pointer, * inserting_unit;
pointer=(*root);
run_pointer=NULL;
//-----NEW UNIT------
inserting_unit=(unit *)malloc(sizeof(struct unit));
inserting_unit->left=NULL;
inserting_unit->right=NULL;
inserting_unit->parent=NULL;
inserting_unit->key=element;
//-------------------
while (pointer!=NULL)
{
run_pointer=pointer;
if (element<pointer->key) pointer=pointer->left;
else pointer=pointer->right;
}
inserting_unit->parent=run_pointer;
if (run_pointer==NULL) (*root)=inserting_unit;
else if (inserting_unit->key<run_pointer->key)
run_pointer->left=inserting_unit;
else run_pointer->right=inserting_unit;
}
//-----INITIALIZATION OF TREE--------------
unit * initialization_tree (void)
{
unit * root;
root=(unit *)malloc(sizeof(struct unit));
root->left=NULL;
root->right=NULL;
root->parent=NULL;
printf("\n Enter the key of the root of tree\n");
type_of_element element;
scanf(" %c",&element);
root->key=element;
if (root!=NULL) return root;
else { printf("\n Error\n") ;return NULL;};
}
//---INORDER TREE WALK--------
void inorder_tree_walk(unit * root)
{
if (root!=NULL)
{
inorder_tree_walk(root->left);
printf(" %c",root->key);
inorder_tree_walk(root->right);
};
}
//----------TREE MINIMUM--------------------------
unit * tree_minimum (unit * x)
{
while (x->left!=NULL) x=x->left;
return x;
}
//------------TREE SUCCESSOR----------------------
unit * tree_successor(unit * x)
{
unit * y;
if (x->right!=NULL) return tree_minimum(x->right);
y=x->parent;
while ((y!=NULL) && (x==y->right)) { x=y; y=y->parent;};
return y;
}
//-------------DELETE ELEMENT-----------------------
unit * tree_delete(unit * root, unit * z)
{
unit * y, * x;
if ((z->left==NULL) || (z->right==NULL))
y=z;
else y=tree_successor(z);
if (y->left!=NULL)
x=y->left;
else x=y->right;
if (x!=NULL)
x->parent=y->parent;
if (y->parent==NULL)
root=x;
else if (y==y->parent->left)
y->parent->left=x;
else y->parent->right=x;
if (y!=z)
z->key=y->key;
return y;
}
//--------TREE SEARCH---------------------
unit * tree_search(unit * pointer, type_of_element symbol)
{
if ((pointer==NULL)|| (pointer->key==symbol))
return pointer;
if (symbol<pointer->key)
tree_search(pointer->left,symbol);
else tree_search(pointer->right,symbol);
}
Висновок
Після виконаної роботи я ознайомився iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi бінарних дерев та оволодів методами роботи iз бінарними деревами.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора