Как-то раз я делал задание для приёма на работу после собеседования, что-то вроде тестового задания только не на дом. Был интернет и я гуглил код на языке Си и нашел какой-то код который содержал ошибки, из-за этого я не смог сделать задание на которое выделили час. Почему так случилось скажу лишь то, что по программированию у меня было все плохо по минимуму и своего кода для деревьев у меня не было и для графов тоже.
И так приступим с основ:
Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево не является упорядоченным ориентированным деревом.[1]
//Листинг #1 Бинарное дерево, представление
#include <iostream>
#include <conio.h>
using namespace std;
//Наша структура
struct node
{
int info; //Информационное поле
node *l, *r; //Левая и Правая часть дерева
};
node *tree = NULL; //Объявляем переменную, тип которой структура Дерево
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a, node **t)
{
if ((*t) == NULL) //Если дерева не существует
{
(*t) = new node; //Выделяем память
(*t)->info = a; //Кладем в выделенное место аргумент a
(*t)->l = (*t)->r = NULL; //Очищаем память для следующего роста
return; //Заложили семечко, выходим
}
//Дерево есть
if (a > (*t)->info) push(a, &(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
else push(a, &(*t)->l); //Иначе кладем его влево
}
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print(node *t, int u)
{
if (t == NULL) return; //Если дерево пустое, то отображать нечего, выходим
else //Иначе
{
print(t->l, ++u); //С помощью рекурсивного посещаем левое поддерево
for (int i = 0; i < u; ++i) cout << "|";
cout << t->info << endl; //И показываем элемент
u--;
}
print(t->r, ++u); //С помощью рекурсии посещаем правое поддерево
}
int sum(node *node_) {
if (node_ == 0) return 0;
return node_->info + sum(node_->l) + sum(node_->r);
}
int main()
{
int n = 16; //Количество элементов
int s; //Число, передаваемое в дерево
for (int i = 0; i < n; ++i)
{
s = -5 + rand() % 10; //Считываем элемент за элементом
push(s, &tree); //И каждый кладем в дерево
}
cout << "ваше дерево\n";
print(tree, 0);
cout << "сумма\n"<<
sum(tree) << endl;
cin.ignore().get();
}
Данный код задает дерево и считает рекурсивно сумму его вершин. Дерево неупорядочено и не отсортировано.
Может быть мне или кому-нибудь еще пригодится данный код для устройства на работу, просто сейчас очень многие постят код который с ошибками в глуповатых статьях и сайтах.
Спасибо за внимание!
Источник статьи: https://habr.com/ru/post/564848/
И так приступим с основ:
Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево не является упорядоченным ориентированным деревом.[1]
//Листинг #1 Бинарное дерево, представление
#include <iostream>
#include <conio.h>
using namespace std;
//Наша структура
struct node
{
int info; //Информационное поле
node *l, *r; //Левая и Правая часть дерева
};
node *tree = NULL; //Объявляем переменную, тип которой структура Дерево
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a, node **t)
{
if ((*t) == NULL) //Если дерева не существует
{
(*t) = new node; //Выделяем память
(*t)->info = a; //Кладем в выделенное место аргумент a
(*t)->l = (*t)->r = NULL; //Очищаем память для следующего роста
return; //Заложили семечко, выходим
}
//Дерево есть
if (a > (*t)->info) push(a, &(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
else push(a, &(*t)->l); //Иначе кладем его влево
}
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print(node *t, int u)
{
if (t == NULL) return; //Если дерево пустое, то отображать нечего, выходим
else //Иначе
{
print(t->l, ++u); //С помощью рекурсивного посещаем левое поддерево
for (int i = 0; i < u; ++i) cout << "|";
cout << t->info << endl; //И показываем элемент
u--;
}
print(t->r, ++u); //С помощью рекурсии посещаем правое поддерево
}
int sum(node *node_) {
if (node_ == 0) return 0;
return node_->info + sum(node_->l) + sum(node_->r);
}
int main()
{
int n = 16; //Количество элементов
int s; //Число, передаваемое в дерево
for (int i = 0; i < n; ++i)
{
s = -5 + rand() % 10; //Считываем элемент за элементом
push(s, &tree); //И каждый кладем в дерево
}
cout << "ваше дерево\n";
print(tree, 0);
cout << "сумма\n"<<
sum(tree) << endl;
cin.ignore().get();
}
Данный код задает дерево и считает рекурсивно сумму его вершин. Дерево неупорядочено и не отсортировано.
Может быть мне или кому-нибудь еще пригодится данный код для устройства на работу, просто сейчас очень многие постят код который с ошибками в глуповатых статьях и сайтах.
Спасибо за внимание!
Источник статьи: https://habr.com/ru/post/564848/