Отчет ЛР3 МО-
.docxФедеральное государственное бюджетное образовательное учреждение
высшего образования
Уфимский государственный авиационный технический университет
Кафедра вычислительной математики и кибернетики
Лабораторная работа №3
« Построение бинарного дерева »
Выполнил:
студент группы МО-
Проверил:
Рипатти А.В.
Уфа – 2020
Задача: Построить поисковое дерево из 28 четырёхзначных элементов и сделать 3 правосторонних обхода.
Теория:
Если дерево организовано так, что для каждой вершины ti справедливо утверждение, что все ключи левого поддерева ti меньше ключа ti , а все ключи правого поддерева ti больше его, то такое дерево будем называть деревом поиска или поисковым деревом.
Используемый язык программирования: С++
Реализация:
#include <iostream>
#include<conio.h>
#include <Windows.h>
#include <time.h>
using namespace std;
struct node
{
int x;
node* left, * right;
node() {
cout << "Поисковое дерево" << endl;
}
node(int key) {
x = key;
left = nullptr;
right = nullptr;
}
~node() {
if (left)
delete left;
if (right)
delete right;
}
void set(int x) {
this->x = x;
}
};
node* insert(node* root, int val) {
if (root == nullptr)
return new node(val);
if (val < root->x)
root->left = insert(root->left, val);
if (val > root->x)
root->right = insert(root->right, val);
return root;
}
int rrand(int range_min, int range_max) {
return rand() % (range_max - range_min + 1) + range_min;
}
void Symmetric(node* pCurrent, int level) {
if (pCurrent != NULL) {
Symmetric(pCurrent->right, level + 1); //обработка всех правых поддеревьев
string str; //обработка корневой вершины pCurrent
for (int i = 0; i < level; i++)
str += " ";
cout << " " << str << pCurrent->x << "\n";
Symmetric(pCurrent->left, level + 1); //обработка всех левых поддеревьев
}
}
void NRL(node* pCurrent, int level) {
if (pCurrent != NULL) {
cout << " " << pCurrent->x;
NRL(pCurrent->right, level + 1);
NRL(pCurrent->left, level + 1);
}
}
void RNL(node* pCurrent, int level) {
if (pCurrent != NULL) {
RNL(pCurrent->right, level + 1);
cout << " " << pCurrent->x;
RNL(pCurrent->left, level + 1);
}
}
void RLN(node* pCurrent, int level) {
if (pCurrent != NULL) {
RLN(pCurrent->right, level + 1);
RLN(pCurrent->left, level + 1);
cout << " " << pCurrent->x;
}
}
int main(){
srand(static_cast<unsigned int>(time(NULL)));
setlocale(LC_ALL, "ru");
int a[20];
for (int j = 0; j < 28; ++j) {
a[j] = rrand(1000, 9999);
}
cout << "Массив Элементов" << endl;
for (int j = 0; j < 28; ++j) {
cout << j+1 << ") " << a[j] << " ";
}
cout << endl << endl;
node* tree;
tree = new node(a[0]);
for (int i = 1; i < 28; ++i) {
insert(tree, a[i]);
}
Symmetric(tree, 0);
NRL(tree, 0);
cout << " NRL\n" << endl;
RNL(tree, 0);
cout << " RNL\n" << endl;
RLN(tree, 0);
cout << " RLN\n" << endl;
return 0;
}
Результат работы программы
Вывод: В ходе лабораторной работы научилась поисковое дерево и реализовывать его правосторонние обходы.