Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ
ФИЛИАЛ ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)» в г. Смоленске
Кафедра информатики
Отчет
По лабораторной работе
Тема: «Деревья»
по курсу: «Информатика и программирование»
Студент Группа ПИЭ-
Преподаватель
Вариант 4
Смоленск, 2012
Дерево (структура данных)
Простой пример неупорядоченного дерева
Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.
Определения
Узлы
Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья 'растут' вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.
Корневые узлы
Самый верхний узел дерева называется корневым узлом. Быть самым верхним узлом подразумевает отсутствие у корневого узла предков. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). (Согласно формальному определению, каждый подобный путь должен быть уникальным). В диаграммах он обычно изображается на самой вершине. В некоторых деревьях, например, кучах, корневой узел обладает особыми свойствами. Каждый узел дерева можно рассматривать как корневой узел поддерева, «растущего» из этого узла.
Листовые узлы
Узлы самого нижнего уровня дерева называются листовыми узлами или листьями. Так как они находятся на самом нижнем уровне, они не имеют никаких потомков.
Внутренние узлы
Внутренний узел — любой узел дерева, имеющий потомков, и, таким образом, не являющийся листовым узлом.
Поддеревья
Поддерево — часть деревообразной структуры данных, которая может быть представлено в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).
Упорядочивание деревьев
Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными рёбрами или упорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.
Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска — одно из разновидностей упорядоченного дерева.
Методы обхода
Пошаговый перебор элементов дерева по связям между предками-узлами и потомками-узлами называется обходом дерева, а сам процесс называется обходом по дереву. Зачастую, операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.
Работа с двоичными деревьями. Произвести поиск количества нечетных элементов. Совершить обходы: ПЛК, ЛПК.
Для выполнения задания необходимо создать само дерево, добавить в него элементы. Для нахождения количества нечетных элементов необходимо задать начальное количество нечетных элементов (s), равное «0», затем проверить каждый элемент, и если он нечетный, s:=s+1. Произвести обходы: ПЛК (Правая-Левая-Корень), ЛПК (Левая-Правая-Корень).
Блок-схема Добавления элемента.
Рис. 4.1 – Добавление элемента
Блок-схема процедуры Add.
Рис. 4.2 - Процедура Add
Блок-схема процедуры ShowTree.
Рис. 4.3 - Процедура ShowTree
Блок-схема процедуры Zad.
Рис. 4.4 - Процедура Zad
Блок-схема процедуры ShowTree1.
Блок-схема процедуры ShowTree2.
Рис. 4.5 - Процедура ShowTree1
Рис. 4.6 - Процедура ShowTree2
Модульная структура программы.
Рис. 5.1 – Модульная структура программы
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
pTree=^Tree;
Tree=record
d:Integer;
left,right:pTree;
end;
TForm1 = class(TForm)
Button1: TButton;
Edit1: TEdit;
Memo1: TMemo;
Button2: TButton;
Edit2: TEdit;
Button3: TButton;
Button4: TButton;
procedure Button1Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
pRoot:pTree;
n:Integer=6; k,i:Integer;
Form1: TForm1;
implementation
{$R *.dfm}
procedure CreateTree;
begin
pRoot:=nil;
end;
procedure Add(var a:pTree; x:Integer);
begin
If a<>nil then
begin
If a.d>=x then
begin
If a.left=nil then
begin
New(a.left);
a.left.d:=x;
a.left.left:=nil;
a.left.right:=nil;
end
else
Add(a.left,x);
end
else
begin
If a.right=nil then
begin
New(a.right);
a.right.d:=x;
a.right.left:=nil;
a.right.right:=nil;
end
else
Add(a.right,x);
end;
end
else
begin
New(a);
a.left:=nil;
a.right:=nil;
a.d:=x;
end;
end;
procedure ShowTree(a:pTree);
var s:string;
i:Integer;
begin
k:=k+n;
If a.right<>nil then
ShowTree(a.right);
s:='';
For i:=1 to k-n do
s:=s+' ';
s:=s+IntToStr(a.d);
Form1.Memo1.Lines.Add(s);
If a.left<>nil then
ShowTree(a.left);
k:=k-n;
end;
procedure TForm1.Button1Click(Sender: TObject);
var x:Integer;
begin
x:=StrToInt(Edit1.Text);
Edit1.Clear;
Add(pRoot,x);
Memo1.Clear;
ShowTree(pRoot);
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
CreateTree;
Memo1.Clear;
end;
procedure Zad(a:pTree);
begin
If (a.d mod 2)<>0 then i:=i+1;
If a.left<>nil then Zad(a.left);
If a.right<>nil then Zad(a.right);
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
zad(pRoot);
Form1.Edit2.Text:=IntToStr(i);
end;
procedure ShowTree1(a:pTree);
begin
If a.right<>nil then ShowTree1(a.right);
If a.left<>nil then ShowTree1(a.left);
Form1.Memo1.Lines.Add(IntToStr(a.d));
end;
procedure ShowTree2(a:pTree);
begin
If a.left<>nil then ShowTree2(a.left);
If a.right<>nil then ShowTree2(a.right);
Form1.Memo1.Lines.Add(IntToStr(a.d));
end;
procedure TForm1.Button3Click(Sender: TObject);
var S:string;
begin
Memo1.Clear;
s:='';
Memo1.Lines.Add(S);
ShowTree1(pRoot);
end;
procedure TForm1.Button4Click(Sender: TObject);
var S:string;
begin
Memo1.Clear;
s:='';
Memo1.Lines.Add(S);
ShowTree2(pRoot);
end;
end.
Рис. 8.1 – Добавление элемента.
Рис. 8.2 – Поиск количества нечетных элементов.
Рис. 8.3 – Обход: ПЛК.
Рис. 8.4 – Обход: ЛПК.
В результате выполнения лабораторной работы освоены способы использования деревьев. Было произведено добавление элементов, поиск количества нечетных элементов, обходы: ПЛК, ЛПК.