Лабораторная 3

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра информационной безопасности

отчет

по лабораторной работе №3

по дисциплине «Алгоритмы и структуры данных»

Тема: Рекурсивные алгоритмы

Студент гр. 1363		Жданов Е.М.
Преподаватель		Беляев А.В.

Санкт-Петербург

2022

Теоретическая часть

Обход дерева - вид обхода графа, обусловливающий процесс посещения каждого узла структуры дерева данных ровно один раз. Такие обходы классифицируются по порядку, в котором узлы посещаются. Алгоритмы относятся к двоичным деревьям, но могут быть обобщены и для других деревьев.

В отличие от связных списков, одномерных массивов и других линейных структур данных, которые канонически обходятся в линейном порядке, деревья можно обходить различными путями.. Существует три основных способа обхода:

• прямой (pre-order)

• центрированный (in-order)

• обратный (post-order)

Практическая часть

1. Программа по созданию двоичного дерева, добавления в него элементов, дополненного алгоритмом рекурсивного обхода двоичного дерева: см. Приложение 1.

Обход двоичного дерева, построенного на основе массива (Вариант 11)

Приложение 1

Файл main.c:

#include <iostream>

#include <fstream>

#include <list>

#include "binary_tree.h"

int main() {

tree *Tree = new tree;

CreateHash(hash);

ifstream file(R"(C:\Users\emzhd\CLionProjects\test_bin\ads_lab2.dat)");

if (!file.is_open()) {

std::cout << "File is not opened!" << std::endl;

return 1;

}

int art[100000], creator[100000], article;

float price[100000], s_price;

for (int i = 0; i < 100000; i++) {

file >> art[i] >> price[i] >> creator[i];

if (i == 0) {

CreateTree(Tree, price[i], art[i], creator[i]);

}

else {

AddToTree(Tree, price[i], art[i], creator[i]);

}

}

int result[39]{0};

stats(Tree, result);

std::cout << "Enter the price of the element you want to find in a tree: " << std::endl;

std::cin >> s_price;

SearchInTree(Tree, s_price);

int results[6]{0};

stats(Tree,result);

std::cout<<"Statistics of a tree: "<<std::endl;

std::cout<<std::endl;

int r=0;

for(int i: result){

r++;

std::cout<<r-1<<"\t"<<i<<std::endl;

}

int a=0,*a_ptr;

a_ptr=&a;

recursion(Tree,a_ptr);

return 0;

}

Файл binary_tree.c:

#include <iostream> #include "binary_tree.h" tree* CreateTree(tree* Tree,float key,int art,int creator){ Tree->left= nullptr; Tree->right=nullptr; Tree->key=key; Tree->creator=creator; Tree->atr=art; Tree->height=1; return Tree; } tree* AddToTree(tree* Tree,float key,int art,int creator){ tree* Tree1=new tree(); Tree1->key=key; Tree1->creator=creator; Tree1->atr=art; if(Tree!=nullptr){ if(Tree1->key<Tree->key) { if (Tree->left == nullptr) { Tree->left = Tree1; Tree1->height=Tree->height+1; } else(AddToTree(Tree->left,key,art,creator)); } if(Tree1->key>Tree->key){ if (Tree->right == nullptr) { Tree->right = Tree1; Tree1->height=Tree->height+1; } else(AddToTree(Tree->right,key,art,creator)); } if(Tree1->key==Tree->key){ //std::cout<<Tree->key<<" "<<key<<std::endl; Tree->middle.push_back(Tree1); } } Tree1->left=nullptr; Tree1->right=nullptr; return Tree; } tree* SearchInTree(tree* Tree,float key) { if (Tree == nullptr) { return Tree; } else { if (Tree->key == key) { cout << Tree->atr << " " << Tree->key << " " << Tree->creator << "\n"; if (!Tree->middle.empty()) { for (tree *i: Tree->middle){ cout << i->atr << " " << i->key << " " << i->creator << "\n"; } } } if (key > Tree->key) { if(Tree->right==nullptr){ std::cout<<"There is no such element with this price"<<std::endl; } else return SearchInTree(Tree->right, key); } if (key < Tree->key) { if(Tree->left==nullptr){ std::cout<<"There is no such element with this price"<<std::endl; } else return SearchInTree(Tree->left, key); } return Tree; } } int* stats(tree* Tree,int result[40]) { if (Tree->left != nullptr && Tree->right != nullptr) { result[Tree->height]++; stats(Tree->left,result); stats(Tree->right,result); } else { if (Tree->left != nullptr) { { result[Tree->height]++; stats(Tree->left,result); } } if (Tree->right != nullptr) { { result[Tree->height]++; stats(Tree->right, result); } } } return result; }

int recursion(tree *root,int* ctr) {

if(root==nullptr){

return 0;

}

else{

recursion(root->left,ctr);

(*ctr)++;

if((*ctr>=0&&*ctr<=10)||(*ctr>=50001&&*ctr<=50010)) {

std::cout << *ctr << " " << root->key << std::endl;

SearchInTree(root,root->key);

}

recursion(root->right,ctr);

}

return 0;

}

Файл binary_tree.h:

#ifndef NEW_LAB_2_AISD_BINARY_TREE_H #define NEW_LAB_2_AISD_BINARY_TREE_H #include <list> #include <iostream> using namespace std; struct tree{ tree* left; tree* right; std::list<tree*> middle; float key; int atr; int creator; int height; }; tree* CreateTree(tree* Tree,float key,int art,int creator); tree* AddToTree(tree* Tree,float key,int art,int creator); tree* SearchInTree(tree* Tree,float key); int* stats(tree* Tree,int result[40]);

int recursion(tree* root, int* ctr); #endif //NEW_LAB_2_AISD_BINARY_TREE_H

Результаты запуска программы (дополненного алгоритма)

Рисунок 1 – результат запуска программы

Рисунок 2 – результат запуска программы

Вывод

Был изучен принцип работы рекурсивных алгоритмов и реализован алгоритм обхода в двоичного дерева с помощью рекурсии