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



Дата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




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




©engime.org 2022
әкімшілігінің қараңыз

    Басты бет