Бинарные деревья

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РФ

Федеральное государственное бюджетное образовательное учреждение высшего образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

ЛАБОРАТОРНАЯ РАБОТА №1

(вариант 14)

по дисциплине «Структуры и алгоритмы обработки данных на ЭВМ»

Студент ______

________

Направления подготовки

______

«__» сентября 20__ г.

Руководитель:

______________

__________ ____________

«__» ___________ 20__ г.

20__

Содержание

1.        Тема работы        3

2.        Цель работы        3

3.        Индивидуальное задание        3

4.        Алгоритм решения задачи        3

5.        Результаты работы программы        4

6.        Выводы        5

Приложение А. Листинг программы        6

1. Тема лабораторной работы № 1 «БИНАРНЫЕ ДЕРЕВЬЯ»

1. Цель лабораторной работы № 1 - получить практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», реализовать на языке программирования C/C++ алгоритмы работы с деревьями.

1. Индивидуальное задание. Вариант 14. Задать последовательность чисел. Написать программу, выполняющую построение и вывод бинарного дерева на экран. Для построенного дерева найти все вершины, имеющие поддеревья одинаковой высоты, и для каждой из этих вершин вывести список потомков. После выполнения программы очистить память, занятую древовидной структурой.

1. Алгоритм решения задачи. Создадим следующие функции:

1 Создание бинарного дерева.
2 Вывод бинарного дерева.
3 Вычисление высоты бинарного дерева.
4 Освобождение памяти, занятой древовидной структурой.

Программа запрашивает у пользователя количество элементов, после чего предлагает ввести их вручную с клавиатуры. Затем мы используем прямой обход бинарного дерева и функцию для вычисления высоты бинарного дерева, выводим узел и высоту его поддеревьев слева и справа. Если высоты поддеревьев совпадают, мы выводим потомков искомого узла. После этого выполняется освобождение памяти, занятой древовидной структурой.

1. Результат работы программы.

Скриншот 1. Вводим необходимые элементы.

[pic 1]

Скриншот 2. Результат работы программы.

[pic 2]

Скриншот 3. Результат работы программы

[pic 3]

1. Выводы.

Программа идентифицирует вершины, у которых поддеревья имеют одинаковую высоту, и выводит список их потомков на экран. Программа была протестирована и демонстрирует корректную работу.

1. Приложение А. Листинг программы.

#include <iostream>

#include <cstdio>

#include <cstring>

#include <stdio.h>

#include <clocale>

#include <math.h>

#include <iomanip>

using namespace std;

struct Node//Структура дерева

{

        int x;

        Node* left, * right;

};

void push(int a, Node*& MyTree) //Функция формирования дерева и добавления узлов

{

        if (MyTree == NULL)

        {

                MyTree = new Node;

                MyTree->x = a;

                MyTree->left = MyTree->right = NULL;

        }

        if (MyTree->x > a)