Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних "Бінарне дерево пошуку"
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2007
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 5
з дисципліни: “Програмування” на тему:
Структура даних „Бінарне дерево пошуку”
Варіант 6
1. Мета роботи
Навчитись працювати з структурою даних “Бінарне дерево пошуку ”.
2. Постановка задачі
Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Виконати обхід дерева у заданому порядку і підрахувати:
кількість вершин дерева, що обраховується при проходженні дерева у прямому порядку;
кількість листків дерева, що обраховується при проходженні дерева у зворотньому порядку;
кількість вузлів, які мають тільки одного нащадка, що обраховується при проходженні дерева у симетричному порядку.
Побудувати два бінарних дерева пошуку. Визначити, чи можна одне дерево одержати з іншого шляхом вилучення однієї вершини.
3. Алгоритм розв’язання задачі
Ініціалізувати бінарне дерево пошуку№1
Вивести на екран рядок “Enter tree #1:”
Вивести на екран рядок “Enter int element (0 - finish):”
Ввести з клавіатури число x
Якщо x≠0, то додати x в бінарне дерево пошуку№1
Якщо x≠0, то перейти до пункту 3
Роздрукувати бінарне дерево пошуку№1
Вивести на екран кількість вершин, листків, вузлів, які мають тільки одного нащадка, для бінарного дерева пошуку№1
Ініціалізувати бінарне дерево пошуку№2
Вивести на екран рядок “Enter tree #2:”
Вивести на екран рядок “Enter int element (0 - finish):”
Ввести з клавіатури число x
Якщо x≠0, то додати x в бінарне дерево пошуку№2
Якщо x≠0, то перейти до пункту 11
Роздрукувати бінарне дерево пошуку№2
Вивести на екран кількість вершин, листків, вузлів, які мають тільки одного нащадка, для бінарного дерева пошуку№2
Якщо з бінарного дерева пошуку№1 можна видалити якусь вершину, і при цьому воно співпаде з бінарним деревом пошуку№2 або якщо з бінарного дерева пошуку№2 можна видалити якусь вершину, і при цьому воно співпаде з бінарним деревом пошуку№1, то вивести на екран рядок “Yes”, в іншому разі вивести на екран рядок “No”
4. Текст програми
#include <stdio.h>
#include "pBTREE.c"
void MakeCopyTree(binary_tree rootF,binary_tree * rootT);
void DestroyTree(binary_tree root);
int NumPeaks(binary_tree root, binary_tree knot){
int num=0;
if (knot)
{
if (WhoFather(root,knot)&&(WhoLeft(knot)||WhoRight(knot))) num++;
num+=NumPeaks(root,WhoLeft(knot));
num+=NumPeaks(root,WhoRight(knot));
};
return num;
}
int NumLeafs(binary_tree knot){
int num=0;
if (knot){
num+=NumLeafs(WhoLeft(knot));
num+=NumLeafs(WhoRight(knot));
if ((!WhoLeft(knot))&(!WhoRight(knot))) num++;
}
return num;
}
int NumElem(binary_tree knot){
int num=0;
if (knot){
num+=NumElem(WhoLeft(knot));
num++;
num+=NumElem(WhoRight(knot));
}
return num;
}
int GoSym(binary_tree knot){
int num=0;
if (knot){
num+=GoSym(WhoLeft(knot));
if (NumElem(knot)==2) num++;
num+=GoSym(WhoRight(knot));
}
return num;
}
int TreesEq(binary_tree root1,binary_tree root2){
if ((!root1)&&(!root2)) return 1;
if ((root1)&&(root2)){
if (root1->data!=root2->data) return 0;
if (!TreesEq(WhoLeft(root1),WhoLeft(root2))) return 0;
if (!TreesEq(WhoRight(root1),WhoRight(root2))) return 0;
return 1;
}
return 0;
}
int Test1(binary_tree root1,binary_tree root2,binary_tree knot){
int data1,ret;
binary_tree btt;
if (knot){
if (WhoFather(root1,knot)&&(WhoLeft(knot)||WhoRight(knot))){
MakeCopyTree(root1,&btt);
data1=knot->data;
DeleteSearchTree(&btt, data1);
ret=0;
if (TreesEq(btt,root2)) ret=1;
DestroyTree(btt);
if (ret) return 1;
}
if (Test1(root1,root2,WhoLeft(knot))) return 1;
if (Test1(root1,root2,WhoRight(knot))) return 1;
}
return 0;
}
void DestroyTree(binary_tree root){
if (root){
DestroyTree(WhoLeft(root));
DestroyTree(WhoRight(root));
free(root);
}
}
void MakeCopyTreeH(binary_tree rootF,binary_tree * rootT){
if (rootF){
*rootT=MakeNode(rootF->data);
MakeCopyTreeH(WhoLeft(rootF),&((*rootT)->leftson));
MakeCopyTreeH(WhoRight(rootF),&((*rootT)->rightson));
} else
{
*rootT=NULL;
}
}
void MakeCopyTree(binary_tree rootF,binary_tree * rootT){
Init(rootT);
MakeCopyTreeH(rootF,rootT);
}
int main(void){
binary_tree bt1,bt2;
int x;
//Tree 1
Init(&bt1);
printf("Enter tree #1:\n");
do {
printf("Enter int element (0 - finish):");
scanf("%d",&x);
if (x) AddSearchTree(&bt1,x);
} while (x);
PrintTurningTree(bt1,0);
printf("Number of peaks:%d\n",NumPeaks(bt1,bt1));
printf("Number of leafs:%d\n",NumLeafs(bt1));
printf("Number of knots with 1 descendant:%d\n",GoSym(bt1));
//Tree 2
Init(&bt2);
printf("Enter tree #2:\n");
do {
printf("Enter int element (0 - finish):");
scanf("%d",&x);
if (x) AddSearchTree(&bt2,x);
} while (x);
PrintTurningTree(bt2,0);
printf("Number of peaks:%d\n",NumPeaks(bt2,bt2));
printf("Number of leafs:%d\n",NumLeafs(bt2));
printf("Number of knots with 1 descendant:%d\n",GoSym(bt2));
if (Test1(bt1,bt2,bt1)||Test1(bt2,bt1,bt2)) printf("Yes\n"); else printf("No\n");
return 0;
}
5. Результати виконання програми
Enter tree #1:
Enter int element (0 – finish):1
Enter int element (0 – finish):2
Enter int element (0 – finish):3
Enter int element (0 – finish):0
3
2
1
Number of peaks:1
Number of leafs:1
Number of knots with 1 descendant:1
Enter tree #2:
Enter int element (0 – finish):1
Enter int element (0 – finish):3
Enter int element (0 – finish):0
3
1
Number of peaks:0
Number of leafs:1
Number of knots with 1 descendant:1
Yes
6. Графічне представлення
Бінарне дерево пошуку№1
Бінарне дерево пошуку№2
root↓
free↓
free↓
root↓
індекси
0
1
2
3
4
5
індекси
0
1
2
3
4
5
data
0
2
1
6
3
7
data
0
3
4
3
5
1
father
0
2
0
5
1
0
father
0
5
0
4
2
0
leftson
0
0
0
0
0
0
leftson
0
0
0
0
0
0
rightson
0
4
1
0
0
3
rightson
0
0
4
0
3
1
7. Висновки
З допомогою цієї лабораторної роботи я навчився працювати з структурою даних “Бінарне дерево пошуку ”.
06.03.2013 23:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора