ЛР3. ЛР3_ГаллямовФР. Отчет по лабораторной работе 3 по дисциплине Алгоритмы и структуры данных

• Название: Отчет по лабораторной работе 3 по дисциплине Алгоритмы и структуры данных
• Дата: 11.06.2022
• Размер: 239.1 Kb.
• Имя файла: ЛР3_ГаллямовФР.docx
• Тип: Отчет; #584712

ФГБОУ ВО

Уфимский государственный авиационный технический университет

Кафедра ВМиК

Отчет

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

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

Построение бинарных деревьев, представленных массивами

Выполнил:

ст. гр. ЦТКС-102м

Галлямов Ф.Р.

Проверила:

Верхотурова Г.Н.

Уфа 2022
Цель работы

Целью работы является построение дерева заданной структуры и прохождение его в заданном порядке.
Задание
Сгенерировать 25 неповторяющихся двухзначных элементов.
Вывести их на экран.
Показать процесс построения Min-Heap-Tree.
Вывести на экран полученное дерево.
Дополнительное задание: в отчете перечислить последовательность
вершин построенного Min-Heap-Tree, соответствующую прямому порядку
прохождения с приоритетом направо (NRL).
Определение заданного дерева

Представляемые массивами деревья находят применение в приложениях с пирамидами (heaps), являющимися законченными бинарными деревьями, имеющими упорядочение узлов по уровням.

Min-heap-tree, или куча— такое двоичное дерево, для которого выполнены три условия:

1. Значение в любой вершине не больше, чем значения ее потомков.

2. Глубина всех листьев (расстояние до корня) отличается не более чем на 1 уровень.

3. Последний уровень заполняется слева направо без «дырок».

В куче элементы хранятся в виде двоичного дерева, то есть у элементов есть два потомка - левый и правый. В вершине кучи находится один элемент, у него - два потомка на следующем уровне, у них, в свою очередь, по два потомка на третьем уровне (итого - 4 элемента на третьем уровне) и т. д.

Уровни заполняются в порядке увеличения номера уровня, а сам уровень заполняется слева направо. У элементов последнего уровня нет ни одного потомка, возможно, что и у некоторых элементов предпоследнего уровня нет потомков. Также в куче может быть один элемент, у которого только один потомок (левый).
Входные и выходные данные

Входные данные: массив неповторяющихся двузначных чисел, количество элементов массива m = 25.

Выходные данные: min-heap-деревоheapOfTree [] в виде массива и в виде дерева, строка элементовheapOfTree[], поле заданного прохождения дерева.
Алгоритм построения дерева

1. 
   По очереди добавляем элементы массива.
   
2. 
   Первый элемент записывается как родительский.
   
3. 
   Пока родительский элемент больше, чем новый добавленный элемент.
   

Новый введенный элемент меняем местами с родительским элементом.

4. 
   Когда родительский элемент становится меньше, на выходе имеем min-heap дерево.
   

Алгоритм прохождения дерева
Прямой метод прохождения определяется посещением узла в первую
очередь и последующим прохождением сначала левого, а потом правого
поддеревьев (NLR).
Порядок операций при прямом методе прохождения следующий:
1. Посещение узла.
2. Прохождение левого поддерева.
3. Прохождение правого поддерева.
Примеры работы программы

На экран выводится последовательность сгенерированных исходных данных. Далее выводится полученное Min-heap-дерево в виде массива и в виде дерева.

Затем на экран выводится результат симметричного прохождения по дереву (RNL). Результат работы представлен на рисунке 1.



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

import math
import random


class BinHeap:
def __init__(self, array):
self.heapList = array
self.size = len(array)

def percUp(self):
i = self.size
while i // 2 >= 0:
if self.heapList[i] < self.heapList[i // 2]:
self.heapList[i // 2], self.heapList[i] = self.heapList[i], self.heapList[i // 2]

if i == 0:
break
i = i // 2

def insert(self, k):

self.heapList.append(k)
print('Массив после добавления элемента ')
print(self.heapList)
self.percUp()
print('Массив после сортировки ')
print(self.heapList)

def minChild(self, i):
l = 2 * i + 1
r = 2 * i + 2
if r > self.size:
return l
else:
if self.heapList[l] < self.heapList[r]:
return l
else:
return r

def Heap(self, pos):
while (2 * pos + 2) < self.size:
mc = self.minChild(pos)
if self.heapList[pos] > self.heapList[mc]:
self.heapList[pos], self.heapList[mc] = self.heapList[mc], self.heapList[pos]
pos = mc

def delete(self, value):
print('Изначальный массив ')
print(self.heapList)
try:
index = self.heapList.index(int(value))
except:
raise
self.size -= 1
self.heapList[index], self.heapList[-1] = self.heapList[-1], self.heapList[index]
print('Массив перед удалением ')
print(self.heapList)
self.heapList.pop(-1)
print('Сортировка:')
self.build()

def build(self):
print('Изначальный массив ')
print(self.heapList)
self.size = len(self.heapList)
i = self.size // 2
while (i >= 0):
self.Heap(i)
i = i - 1
print('Массив после сортировки ')
print(self.heapList)

def pprint(self):
j = 0
li = []
while j ** 2 <= self.size:
print(' ' * (self.size - j ** 2), end='')
li.append(self.heapList[2 ** (j) - 1: 2 ** (j + 1) - 1])
for y in range(len(self.heapList[2 ** (j) - 1: 2 ** (j + 1) - 1])):
if y == math.floor(((2 ** (j + 1) - 1) - 2 ** (j) - 1) / 2) + 1 and y != 0:
print(' | ', end='')
print(self.heapList[2 ** (j) - 1: 2 ** (j + 1) - 1][y], end=' ')
# print(self.heapList[2**(j)-1: 2**(j+1)-1])
j += 1
print()
j = 5

N = 25
bh = BinHeap([random.randint(10, 99) for i in range(N)])
bh.build()
# print('Добавление')
# num2 = int(input())
# bh.insert(num2)
#
# #while True:
# print('Удаление')
# num = input()
# bh.delete(num)

bh.pprint()
Вывод

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