Бинарные деревья по дисциплине

жүктеу/скачать 0,52 Mb.

Дата	11.04.2022
өлшемі	0,52 Mb.
	#138839

Байланысты:
Bolotnikov Chayka P 3

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ государственное БЮДЖЕТНОЕ
образовательное учреждение
высшего образования
«НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра автоматизированных систем управления

ОТЧЁТ
по практической работе № 3
по теме: Бинарные деревья.
по дисциплине: Программирование.

Вариант №2

Выполнили работу:
Студенты гр. АП-127, АВТФ
Болотников Михаил Станиславович,
Чайка Павел Андреевич Лилия Александровна
«_» марта 2022г
Проверила работу:
Ассистент каф. АСУ
Баранова Нина Владимировна

«___» ______ 20__г

________________
(подпись)

Задание:
Найти сумму элементов идеально сбалансированного дерева, находящихся на уровне k.

Тестовые данные:

Ввод и изображение бинарного дерева	Вывод
15 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 3	Сумма элементов уровня 3 = 64
7 6, 4, 7, 5, 3, 9, 8 2	Сумма элементов уровня 2 = 17

Этапы решения задачи рекурсивным способом:

1)Параметризация задачи: Дерево, уровень.
2)Тривиальный случай: k = 0.
3)Декомпозиция общего случая: Дойти до всех элементов уровня k и записать их сумму.
Блок-схемы рекурсивных функций:

Листинг программы с комментариями

#include

//Структура ветки

struct Branch
{
int Data; //Поле данных
Branch* LeftBranch; //УКАЗАТЕЛИ на соседние веточки
Branch* RightBranch;
};

//Функция внесения данных

void Add(int aData, Branch*& aBranch)
{
//Если ветки не существует
if (!aBranch)
{ //создадим ее и зададим в нее данные
aBranch = new Branch;
aBranch->Data = aData;
aBranch->LeftBranch = 0;
aBranch->RightBranch = 0;
return;
}
else //Иначе сверим вносимое
if (aBranch->Data > aData)
{ //Если оно меньше того, что в этой ветке - добавим влево
Add(aData, aBranch->LeftBranch);
}
else
{
Add(aData, aBranch->RightBranch);
};
}

// функция для суммы элементов уровня k, где 0 - это корень дерева

int summ_k(Branch*& aBranch, int d, int k) {
if (aBranch != NULL) {
d++;
if (d < k) {
int sum = 0;
sum += summ_k(aBranch->LeftBranch, d, k);
sum += summ_k(aBranch->RightBranch, d, k);
return sum;
}
else return aBranch->Data;
}
else return 0;
}

int main()

{
setlocale(LC_ALL, "rus");
Branch* Root = 0;
int sum=0, k, l, vel, d ;
printf( "Введите кол-во элементов для будущего дерева: ");
scanf_s("%d", &vel);
printf("Введите элементы дерева:\n");
for (int i = 0; i < vel; i++)
{
scanf_s("%d", &l);
Add(l, Root);
}
printf("Введите уровень( 0 - это корень дерева): ");
scanf_s("%d", &k);
d = -1;
sum = summ_k(Root, d, k);
printf("Сумма элементов уровня %d = %d", k, sum);
}

Новосибирск, 2022

жүктеу/скачать 0,52 Mb.

Достарыңызбен бөлісу: