Структуры данных «дерево» (Pascal/С)

Цель работы: изучить СД «дерево», научиться их программно реализовывать и использовать.

З а д а н и е

1. Для СД «дерево» определить:

1.1. Абстрактный уровень представления СД:

1.1.1. Характер организованности и изменчивости.

1.1.2. Набор допустимых операций.

1.2. Физический уровень представления СД:

1.2.1. Схему хранения.

1.2.2. Объем памяти, занимаемый экземпляром СД.

1.2.3. Формат внутреннего представления СД и способ его интерпретации.

1.2.4. Характеристику допустимых значений.

1.2.5. Тип доступа к элементам.

1.3. Логический уровень представления СД.

Способ описания СД и экземпляра СД на языке программирования.

2. Реализовать СД «дерево» в соответствии с вариантом индивидуального (табл.17) задания в виде модулей на языках Pascal и С.

3. Разработать программы на языках Pascal и С для решения задачи в соответствии с вариантом индивидуального задания (см. табл.17) с использованием модулей, полученных в результате выполнения пункта 2 задания.

Таблица 17

Варианты индивидуальных заданий

Номер варианта	Номер модуля	Варианты задач

Окончание табл.17

Варианты задач

Вариант 1

a) Построить дерево арифметического выражения, заданного в ОПЗ.

Операнды — целочисленные константы.

Операции — «+», «–», «*» и «div».

б) Вывести арифметическое выражение в ППЗ.

в) Вычислить значение по дереву арифметического выражения.

Вариант 2

а) Построить дерево арифметического выражения, заданного в ППЗ. Операнды — целочисленные константы.

Операции — «+», «–», «*» и «div».

б) Вывести арифметическое выражение в ОПЗ.

в) Вычислить значение по дереву арифметического выражения и выводит результат выполнения каждой операции в виде:

<операнд><операция><операнд>=<значение>

Вариант 3

а) Построить упорядоченное сбалансированное дерево T.

M — упорядоченный массив.

б) Вычислить высоту дерева.

в) Вывести дерево по уровням (в i-ю строку вывода — вершины i-го

уровня).

Вариант 4

а) Построить дерево по его скобочному представлению.

б) Вывести все пути от корня к листьям дерева (в i-ю строку вывода — i-й путь).

в) Вывести листья дерева.

Вариант 5

а) Построить упорядоченное дерево.

б) Вывести упорядоченную по возрастанию последовательность, составленную из элементов дерева.

в) Вывести упорядоченную по убыванию последовательность, составленную из элементов дерева.

Вариант 6

а) Построить дерево в ширину.

б) Вычислить количество вершин дерева T, имеющих n сыновей.

в) Вывести выводит самый длинный путь от корня до листа.

Вариант 7

а) Построить дерево в глубину.

б) Определить количество вершин в дереве T на n-ом уровне.

в) Вывести выводит все пути от листьев до корня (в i-ю строку вывода — i-ый путь).

Вариант 8

а) Построить упорядоченное дерево.

б) Вывести упорядоченную по возрастанию последовательность, составленную из элементов дерева, меньших k.

в) Вывести вершины, для которых левое и правое поддерево имеют равное количество вершин.

Вариант 9

а) Построить упорядоченное дерево.

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

в) Вывести количество вершин в левом и в правом поддереве для каждой вершины дерева.

Вариант 10

а) Построить дерево по его скобочному представлению.

б) Создать копию дерева.

в) Сравнить два дерева на равенство.

Модули

1. Дерево в динамической памяти (базовый тип определяется задачей).

Спецификация СД на языке Pascal:

Unit Tree1;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

Type BaseType = …; {определить!!!}

PtrEl = ^Element;

Element = Record

Data: BaseType;

LSon,RSon: PtrEl;

End;

Tree= ^PtrEl;

Var TreeError: 0..2;

Procedure InitTree(var T:Tree); {инициализация — создается элемент, который будет содержать корень дерева}

Procedure CreateRoot(var T:Tree); {создание корня}

Procedure WriteDataTree(var T:Tree; E:BaseType);{запись данных}

Procedure ReadDataTree(var T:Tree; var E:BaseType);{чтение}

Function IsLSon(var T:Tree):boolean;{есть левый сын?}

Function IsRSon(var T:Tree):boolean;{есть правый сын?}

Procedure MoveToLSon(var T,TS:Tree); {перейти к левому сыну, где T — адрес ячейки, содержащей адрес текущей вершины, TS — адрес ячейки, содержащей адрес корня левого поддерева(левого сына)}

Procedure MoveToRSon(var T,TS:Tree); {перейти к правому сыну}

Function IsEmptyTree(var T:Tree):boolean;{пустое дерево?}

Procedure DelTree(var T:Tree);{удаление листа}

Спецификация СД на языке C:

#if!defined(__TREE1_H)

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef /*определить!!!*/ BaseType;

typedef struct element *ptrel;

typedef struct element{basetype data;

ptrel LSon;

ptrel RSon;}

typedef PtrEl *Tree;

short TreeError;

void InitTree(Tree *T)// инициализация — создается элемент, который будет содержать корень дерева

void CreateRoot(Tree *T) //создание корня

void WriteDataTree(Tree *T, BaseType E) //запись данных

void ReadDataTree(Tree *T,BaseType *E)//чтение

int IsLSon(Tree *T)//1 — есть левый сын, 0 — нет

int IsRSon(Tree *T)//1 — есть правый сын, 0 — нет

void MoveToLSon(Tree *T, Tree *TS)// перейти к левому сыну, где T — адрес ячейки, содержащей адрес текущей вершины, TS — адрес ячейки, содержащей адрес корня левого поддерева(левого сына)

void MoveToRSon(Tree *T, Tree *TS)//перейти к правому сыну

int IsEmptyTree(Tree *T)//1 — пустое дерево,0 — не пустое

void DelTree(Tree *T)//удаление листа

#endif

2. Элементы дерева находятся в массиве MemTree, расположенном в статической памяти. Базовый тип зависит от задачи. «Свободные» элементы массива объединяются в список (ССЭ), на начало которого указывает левый сын первого элемента массива. В массиве MemTree

могут располагаться несколько деревьев.

Спецификация СД на языке Pascal:

Unit Tree2;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

SizeMem = 100;

Type BaseType = …; {определить!!!}

Index = 0..SizeMem;

PtrEl = Index;

Element = Record

Data: BaseType;

LSon,RSon: PtrEl;

End;

Tree = ^PtrEl;

Var TreeError: 0..2;

MemTree: array[Index] of Element;

Procedure InitTree(var T:Tree); {инициализация}

Procedure CreateRoot(var T:Tree); {создание корня}

Procedure WriteDataTree(var T:Tree; E:BaseType);{запись данных}

Procedure ReadDataTree(var T:Tree; var E:BaseType);{чтение}

Function IsLSon(var T:Tree):boolean;{есть левый сын?}

Function IsRSon(var T:Tree):boolean;{есть правый сын?}

Procedure MoveToLSon(var T,TS:Tree); {перейти к левому сыну, где T — адрес ячейки, содержащей адрес текущей вершины, TS — адрес ячейки, содержащей адрес корня левого поддерева(левого сына)}

Procedure MoveToRSon(var T,TS:Tree); {перейти к правому сыну}

Function IsEmptyTree(var T:Tree):boolean;{пустое дерево?}

Procedure DelTree(var T:Tree);{удаление листа}

Implementation

Procedure InitMem; forward; {связывает все элементы массива в

список свободных элементов}

Function EmptyMem: boolean; forward; {возвращает TRUE, если в

массиве нет свободных элементов}

Function NewMem: word; forward; {возвращает номер свободного

элемента и исключает его из ССЭ}

Procedure DisposeMem(n:word); forward; {делает n-й элемент мас-

сива свободным и включает его в ССЭ}

Спецификация СД на языке C:

#if!defined(__TREE2_H)

#define SizeMem 100

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef /*определить!!!*/ BaseType;

typedef unsigned char PtrEl;

typedef struct element{basetype data;

ptrel LSon;

ptrel RSon;}

typedef PtrEl *Tree;

short TreeError;

Element MemTree[SizeMem];

void InitTree(Tree *T)// инициализация — создается элемент, который будет содержать корень дерева

void CreateRoot(Tree *T) //создание корня

void WriteDataTree(Tree *T, BaseType E) //запись данных

void ReadDataTree(Tree *T,BaseType *E)//чтение

int IsLSon(Tree *T)//1 — есть левый сын, 0 — нет

int IsRSon(Tree *T)//1 — есть правый сын, 0 — нет

void MoveToLSon(Tree *T, Tree *TS)// перейти к левому сыну, где T — адрес ячейки, содержащей адрес текущей вершины, TS — адрес ячейки, содержащей адрес корня левого поддерева(левого сына)

void MoveToRSon(Tree *T, Tree *TS)//перейти к правому сыну

int IsEmptyTree(Tree *T)//1 — пустое дерево,0 — не пустое

void DelTree(Tree *T)//удаление листа

void InitMem() /*связывает все элементы массива в список свободных элементов*/

int EmptyMem() /*возвращает 1, если в массиве нет свободных элементов, 0 — в противном случае*/

unsigned int NewMem() /*возвращает номер свободного элемента и исключает его из ССЭ*/

void DisposeMem(unsigned n)/*делает n-й элемент массива свободным и включает его в ССЭ*/

#endif

3. Элементы дерева находятся в массиве, расположенном в динамической памяти. Базовый тип зависит от задачи. «Свободные» элементы массива объединяются в список (ССЭ), на начало которого указывает левый сын первого элемента массива. В массиве может

находиться несколько деревьев.

Спецификация СД на языке Pascal:

Unit Tree3;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

Type BaseType = …; {определить!!!}

Index = 0..65520 div sizeof(BaseType);

PtrEl = Index;

Element = Record

Data: BaseType;

LSon,RSon: PtrEl;

End;

Mem = array[Index] of Element;

Pmem = ^Mem;

Tree = ^Ptr: PtrEl;

Var TreeError: 0..2;

Pbuf: Pmem; {указатель на массив}

Size: word; {размер массива}

Procedure InitTree(var T:Tree); {инициализация памяти}

Procedure InitTree(var T:Tree); {инициализация дерева}

Procedure CreateRoot(var T:Tree); {создание корня}

Procedure WriteDataTree(var T:Tree; E:BaseType);{запись данных}

Procedure ReadDataTree(var T:Tree; var E:BaseType);{чтение}

Function IsLSon(var T:Tree):boolean;{есть левый сын?}

Function IsRSon(var T:Tree):boolean;{есть правый сын?}

Procedure MoveToLSon(var T,TS:Tree); {перейти к левому сыну}

Procedure MoveToRSon(var T,TS:Tree); {перейти к правому сыну}

Function IsEmptyTree(var T:Tree):boolean;{пустое дерево?}

Procedure DelTree(var T:Tree);{удаление листа}

Спецификация СД на языке C:

#if!defined(__TREE3_H)

#define Index 1000

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef /*определить!!!*/ BaseType;

typedef unsigned char PtrEl;

typedef struct element{basetype data;

ptrel LSon;

ptrel RSon;}

typedef Element Mem[Index];

typedef Mem *Pmem;

typedef ptrEl* Tree;

short TreeError;

Pmem Pbuf; //указатель на массив//

unsigned Size; //размер массива

void InitTree(Tree *T)// инициализация дерева

void CreateRoot(Tree *T) //создание корня

void WriteDataTree(Tree *T, BaseType E) //запись данных

void ReadDataTree(Tree *T,BaseType *E)//чтение

int IsLSon(Tree *T)//1 — есть левый сын, 0 — нет

int IsRSon(Tree *T)//1 — есть правый сын, 0 — нет

void MoveToLSon(Tree *T, Tree *TS)// перейти к левому сыну, где T — адрес ячейки, содержащей адрес текущей вершины, TS — адрес ячейки, содержащей адрес корня левого поддерева(левого сына)

void MoveToRSon(Tree *T, Tree *TS)//перейти к правому сыну

int IsEmptyTree(Tree *T)//1 — пустое дерево,0 — не пустое

void DelTree(Tree *T)//удаление листа

#endif

4. Элементы дерева находятся в массиве, расположенном в динамической памяти. Базовый тип зависит от задачи. Каждый элемент массива имеет признак того, является ли он элементом дерева или «свободен». Корень дерева находится в первом элементе массива. Для вершины дерева, расположенной в n-м элементе массива, LSon будет находиться в (2*n)-м элементе, а RSon — в (2*n + 1)-м.

Спецификация СД на языке Pascal:

Unit Tree4;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

Type BaseType = …; {определить!!!}

Index = 0..65520 div sizeof(BaseType);

PtrEl = Index;

Element = Record

Data: BaseType;

Flag: Boolean;{FALSE — элемент свободен}

{TRUE - элемент дерева }

End;

Mem = array[Index] of Element;

Pmem= ^Mem;

Tree= record

Pbuf: Pmem; {указатель на массив}

Size: word; {размер массива}

Ptr: PtrEl

end;

Var TreeError: 0..2;

Procedure InitTree(var T:Tree; Size: word); {инициализация}

Procedure CreateRoot(var T:Tree); {создание корня}

Procedure WriteDataTree(var T:Tree; E:BaseType);{запись данных}

Procedure ReadDataTree(var T:Tree;var E:BaseType);{чтение}

Function IsLSon(var T:Tree):boolean;{есть левый сын?}

Function IsRSon(var T:Tree):boolean;{есть правый сын?}

Procedure MoveToLSon(var T:Tree); {перейти к левому сыну}

Procedure MoveToRSon(var T:Tree); {перейти к правому сыну}

Function IsEmptyTree(var T:Tree):boolean;{пустое дерево?}

Procedure DelTree(var T:Tree);{удаление листа}

Спецификация СД на языке C:

#if!defined(__TREE4_H)

#define Index 1000

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef /*определить!!!*/ BaseType;

typedef unsigned char PtrEl;

typedef struct element{basetype data;

short flag;};//0 — элемент занят

//1 — элемент свободен

typedef Element Mem[Index];

typedef Mem *Pmem;

typedef struct Tree{Pmem Pbuf; //указатель на массив

unsigned Size; //размер массива

PtrEl Ptr;};

short TreeError;

void InitTree(Tree *T,unsigned size)// инициализация дерева

void CreateRoot(Tree *T) //создание корня

void WriteDataTree(Tree *T, BaseType E) //запись данных

void ReadDataTree(Tree *T,BaseType *E)//чтение

int IsLSon(Tree *T)//1 — есть левый сын, 0 — нет

int IsRSon(Tree *T)//1 — есть правый сын, 0 — нет

void MoveToLSon(Tree *T, Tree *TS)// перейти к левому сыну, где T — адрес ячейки, содержащей адрес текущей вершины, TS — адрес ячейки, содержащей адрес корня левого поддерева(левого сына)

void MoveToRSon(Tree *T, Tree *TS)//перейти к правому сыну

int IsEmptyTree(Tree *T)//1 — пустое дерево,0 — не пустое

void DelTree(Tree *T)//удаление листа

#endif

5. Дерево в динамической памяти (базовый тип — произвольный).

Спецификация СД на языке Pascal:

Unit Tree5;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

Type BaseType = pointer;

PtrEl = ^Element;

Element = Record

Data: BaseType;

LSon,RSon: PtrEl;

End;

Tree= ^PtrEl;

Var TreeError: 0..2;

SizeEl: word;

Procedure InitTree(var T:Tree; Size: word); {инициализация}

Procedure CreateRoot(var T:Tree); {создание корня}

Procedure WriteDataTree(var T:Tree; E:BaseType);{запись данных}

Procedure ReadDataTree(var T:Tree;var E:BaseType);{чтение}

Function IsLSon(var T:Tree):boolean;{есть левый сын?}

Function IsRSon(var T:Tree):boolean;{есть правый сын?}

Procedure MoveToLSon(var T:Tree); {перейти к левому сыну}

Procedure MoveToRSon(var T:Tree); {перейти к правому сыну}

Function IsEmptyTree(var T:Tree):boolean;{пустое дерево?}

Procedure DelTree(var T:Tree);{удаление листа}

Спецификация СД на языке C:

#if!defined(__TREE5_H)

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef void* BaseType;

typedef struct element *ptrel;

typedef struct element{basetype data;

ptrel LSon;

ptrel RSon;}

typedef PtrEl *Tree;

unsigned Size;

short TreeError;

void InitTree(Tree *T,unsigned size)// инициализация дерева

void CreateRoot(Tree *T) //создание корня

void WriteDataTree(Tree *T, BaseType E) //запись данных

void ReadDataTree(Tree *T,BaseType *E)//чтение

int IsLSon(Tree *T)//1 — есть левый сын, 0 — нет

int IsRSon(Tree *T)//1 — есть правый сын, 0 — нет

void MoveToLSon(Tree *T, Tree *TS)// перейти к левому сыну, где T — адрес ячейки, содержащей адрес текущей вершины, TS — адрес ячейки, содержащей адрес корня левого поддерева(левого сына)

void MoveToRSon(Tree *T, Tree *TS)//перейти к правому сыну

int IsEmptyTree(Tree *T)//1 — пустое дерево,0 — не пустое

void DelTree(Tree *T)//удаление листа

#endif

6. Элементы дерева находятся в массиве MemTree, расположенном в статической памяти. Базовый тип — произвольный. «Свободные» элементы массива объединяются в список (ССЭ), на начало которого указывает левый сын первого элемента массива. В массиве MemTree могут располагаться несколько деревьев.

Спецификация СД на языке Pascal:

Unit Tree6;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

SizeMem = 100;

Type BaseType = pointer;

Index = 0..SizeMem;

PtrEl = Index;

Element = Record

Data: BaseType;

LSon,RSon: PtrEl;

End;

Tree= ^PtrEl;

Var TreeError: 0..2;

MemTree: array[Index] of Element;

SizeEl: word;

Procedure InitTree(var T:Tree; Size: word); {инициализация}

Procedure CreateRoot(var T:Tree); {создание корня}

Procedure WriteDataTree(var T:Tree; E:BaseType);{запись данных}

Procedure ReadDataTree(var T:Tree;var E:BaseType);{чтение}

Function IsLSon(var T:Tree):boolean;{есть левый сын?}

Function IsRSon(var T:Tree):boolean;{есть правый сын?}

Procedure MoveToLSon(var T:Tree); {перейти к левому сыну}

Procedure MoveToRSon(var T:Tree); {перейти к правому сыну}

Function IsEmptyTree(var T:Tree):boolean;{пустое дерево?}

Procedure DelTree(var T:Tree);{удаление листа}

Implementation

Procedure InitMem; forward; {связывает все элементы массива в

список свободных элементов}

Function EmptyMem: boolean; forward; {возвращает TRUE, если в

массиве нет свободных элементов}

Function NewMem: word; forward; {возвращает номер свободного

элемента и исключает его из ССЭ}

Procedure DisposeMem(n:word); forward; {делает n-й элемент мас-

сива свободным и включает его в ССЭ}

Спецификация СД на языке C:

#if!defined(__TREE6_H)

#define Index 1000

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef void *BaseType;

typedef unsigned char PtrEl;

typedef struct element{basetype data;

ptrel LSon;

ptrel RSon;}

typedef PtrEl *Tree;

unsigned Size;

short TreeError;

Element MemTree[Index];

void InitTree(Tree *T,unsigned size)// инициализация дерева

void CreateRoot(Tree *T) //создание корня

void WriteDataTree(Tree *T, BaseType E) //запись данных

void ReadDataTree(Tree *T,BaseType *E)//чтение

int IsLSon(Tree *T)//1 — есть левый сын, 0 — нет

int IsRSon(Tree *T)//1 — есть правый сын, 0 — нет

void MoveToLSon(Tree *T, Tree *TS)// перейти к левому сыну, где T — адрес ячейки, содержащей адрес текущей вершины, TS — адрес ячейки, содержащей адрес корня левого поддерева(левого сына)

void MoveToRSon(Tree *T, Tree *TS)//перейти к правому сыну

int IsEmptyTree(Tree *T)//1 — пустое дерево,0 — не пустое

void DelTree(Tree *T)//удаление листа

void InitMem() /*связывает все элементы массива в список свободных элементов*/

int EmptyMem() /*возвращает 1, если в массиве нет свободных элементов,0 — в противном случае*/

unsigned int NewMem() /*возвращает номер свободного элемента и исключает его из ССЭ*/

void DisposeMem(unsigned n)/*делает n-й элемент массива свободным и включает его в ССЭ*/

#endif

7. Элементы дерева находятся в массиве, расположенном в динамической памяти. Базовый тип - произвольный. «Свободные» элементы массива объединяются в список (ССЭ), на начало которого указывает левый сын первого элемента массива. В массиве может находиться несколько деревьев.

Спецификация СД на языке Pascal:

Unit Tree7;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

Type BaseType = pointer;

Index = 0..65520 div sizeof(BaseType);

PtrEl = Index;

Element = Record

Data: BaseType;

LSon,RSon: PtrEl;

End;

Mem = array[Index] of Element;

Pmem= ^Mem;

Tree=^Ptr: PtrEl;

Var TreeError: 0..2;

Pbuf: Pmem; {указатель на массив}

SizeMem: word; {размер массива}

SizeEl: word; {размер элемента}

Procedure InitTree(var T:Tree; Size: word); {инициализация}

Procedure CreateRoot(var T:Tree); {создание корня}

Procedure WriteDataTree(var T:Tree; E:BaseType);{запись данных}

Procedure ReadDataTree(var T:Tree;var E:BaseType);{чтение}

Function IsLSon(var T:Tree):boolean;{есть левый сын?}

Function IsRSon(var T:Tree):boolean;{есть правый сын?}

Procedure MoveToLSon(var T:Tree); {перейти к левому сыну}

Procedure MoveToRSon(var T:Tree); {перейти к правому сыну}

Function IsEmptyTree(var T:Tree):boolean;{пустое дерево?}

Procedure DelTree(var T:Tree);{удаление листа}

Спецификация СД на языке C:

#if!defined(__TREE7_H)

#define Index 1000

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef void *BaseType;

typedef unsigned PtrEl;

typedef struct element{basetype data;

ptrel LSon;

ptrel RSon;}

typedef Element Mem[Index];

typedef Mem *Pmem;

typedef PtrEl *Tree;

short TreeError;

Pmem Pbuf; //указатель на массив

unsigned Size; //размер массива

unsigned SizeEl;

void InitTree(Tree *T,unsigned size)// инициализация дерева

void CreateRoot(Tree *T) //создание корня

void WriteDataTree(Tree *T, BaseType E) //запись данных

void ReadDataTree(Tree *T,BaseType *E)//чтение

int IsLSon(Tree *T)//1 — есть левый сын, 0 — нет

int IsRSon(Tree *T)//1 — есть правый сын, 0 — нет

void MoveToLSon(Tree *T, Tree *TS)// перейти к левому сыну, где T — адрес ячейки, содержащей адрес текущей вершины, TS — адрес ячейки, содержащей адрес корня левого поддерева(левого сына)

void MoveToRSon(Tree *T, Tree *TS)//перейти к правому сыну

int IsEmptyTree(Tree *T)//1 — пустое дерево,0 — не пустое

void DelTree(Tree *T)//удаление листа

#endif

8. Элементы дерева находятся в массиве, расположенном в динамической памяти. Базовый тип - произвольный. Каждый элемент массива имеет признак того, является ли он элементом дерева или «свободен». Корень дерева находится в первом элементе массива. Для вершины дерева, расположенной в n-м элементе массива, LSon будет находиться в (2*n)-м элементе, а RSon — в (2*n + 1)-м.

Спецификация СД на языке Pascal:

Unit Tree8;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

Type BaseType = pointer;

Index = 0..65520 div sizeof(BaseType);

PtrEl = Index;

Element = Record

Data: BaseType;

Flag: Boolean;{FALSE – элемент свободен}

{TRUE - элемент дерева }

End;

Mem = array[Index] of Element;

Pmem= ^Mem;

Tree= record

Pbuf: Pmem; {указатель на массив}

Size: word; {размер массива}

Ptr: PtrEl

end;

Var TreeError: 0..2;

SizeEl: word; {размер элемента}

Procedure InitTree(var T:Tree; Size: word); {инициализация}

Procedure CreateRoot(var T:Tree); {создание корня}

Procedure WriteDataTree(var T:Tree; E:BaseType);{запись данных}

Procedure ReadDataTree(var T:Tree;var E:BaseType);{чтение}

Function IsLSon(var T:Tree):boolean;{есть левый сын?}

Function IsRSon(var T:Tree):boolean;{есть правый сын?}

Procedure MoveToLSon(var T:Tree); {перейти к левому сыну}

Procedure MoveToRSon(var T:Tree); {перейти к правому сыну}

Function IsEmptyTree(var T:Tree):boolean;{пустое дерево?}

Procedure DelTree(var T:Tree);{удаление листа}

Спецификация СД на языке C:

#if!defined(__TREE8_H)

#define Index 1000

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef void *BaseType;

typedef unsigned PtrEl;

typedef struct element{basetype data;

short flag;};//0 — элемент занят

//1 — элемент свободен

typedef Element Mem[Index];

typedef Mem *Pmem;

typedef struct Tree{Pmem Pbuf; //указатель на массив

unsigned Size; //размер массива

PtrEl Ptr;};

short TreeError;

unsigned SizeEl;//размер элемента

void InitTree(Tree *T,unsigned size)// инициализация дерева

void CreateRoot(Tree *T) //создание корня

void WriteDataTree(Tree *T, BaseType E) //запись данных

void ReadDataTree(Tree *T,BaseType *E)//чтение

int IsLSon(Tree *T)//1 — есть левый сын, 0 — нет

int IsRSon(Tree *T)//1 — есть правый сын, 0 — нет

void MoveToLSon(Tree *T, Tree *TS)// перейти к левому сыну, где T — адрес ячейки, содержащей адрес текущей вершины, TS — адрес ячейки, содержащей адрес корня левого поддерева(левого сына)

void MoveToRSon(Tree *T, Tree *TS)//перейти к правому сыну

int IsEmptyTree(Tree *T)//1 — пустое дерево,0 — не пустое

void DelTree(Tree *T)//удаление листа

#endif

Назначение процедур и функций:

InitTree — инициализация дерева;

CreateRoot — создание корня;

WriteDataTree — запись данных в дерево;

ReadDataTree — чтение элемента дерева;

IsLSon — проверка на наличие левого сына;

IsRSon — проверка на наличие правого сына;

MoveToLSon — переход к левому сыну;

MoveToRSon — переход к правому сыну;

IsEmptyTree — проверка: дерево пусто или нет;

DelTree — удаление листа.

С о д е р ж а н и е о т ч е т а

1. Тема лабораторной работы.

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

3. Характеристика СД «дерево» (п.1 задания).

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

5. Тексты модулей на языках Pascal и С для реализации СД «дерево», тексты программ для отладки модулей, тестовые данные и результат работы программ.

6. Тексты программ на языках Pascal и С для решения задачи с использованием модулей, тестовые данные, результаты работы программ.

Т е о р е т и ч е с к и е с в е д е н и я

Дерево — конечное непустое множество Т, состоящее из одной или более вершин таких, что выполняются следующие условия:

1) Имеется одна специально обозначенная вершина, называемая корнем данного дерева.

2) Остальные вершины (исключая корень) содержатся в m ³ 0 попарно непересекающихся множествах Т₁, Т₂, …, Т_m, каждое из которых в свою очередь является деревом. Деревья Т₁, Т₂, …, Т_m называются поддеревьями данного корня.

Наиболее наглядным способом представления дерева является графический (рис.20), в котором вершины изображаются окружностями с вписанной в них информацией и корень дерева соединяется с корнями поддеревьев Т₁, Т₂, …, Т_m, дугой (линией).

Рис.20. Графический способ представления дерева

Если подмножества Т₁, Т₂, …, Т_m упорядочены, то дерево называют упорядоченным. Если два дерева считаются равными и тогда, когда они отличаются порядком подмножеств Т₁, Т₂, …, Т_m, то такие деревья называются ориентированными деревьями. Конечное множество непересекающихся деревьев называется лесом.

Количество подмножеств для данной вершины называется степенью вершины. Если такое количество равно нулю, то вершина является листом. Максимальная степень вершины в дереве — степень дерева. Уровень вершины — длина пути от корня до вершины. Максимальная длина пути от корня до вершины определяет высоту дерева (количество уровней в дереве).

Бинарное дерево — конечное множество элементов, которое может быть пустым, состоящее из корня и двух непересекающихся бинарных деревьев, причем поддеревья упорядочены: левое поддерево и правое поддерево. В дальнейшем будем рассматривать только СД типа «бинарное дерево» (БД). Корень дерева будем называть «отцом», корень левого поддерева — «левым сыном», а корень правого поддерева — «правым сыном». На рис.21 приведен пример графического представления БД.

уровень 0

уровень 1

уровень 2

уровень 3

Рис.21. Графическое представление БД

БД — динамическая структура. Над СД БД определены следующие основные операции: инициализация, создание корня, запись данных, чтение данных, проверка — есть ли левый сын, проверка — есть ли правый сын, переход к левому сыну, переход к правому сыну, проверка — пустое ли дерево, удаление листа.

Кардинальное число СД БД определяется по формуле

CAR(БД) = (å(2i)! / ((i + 1)(i!)²))·CAR(BaseType) + 1 ,i=1…max,

где CAR(BaseType) — кардинальное число элемента БД типа BaseType, max — максимальное количество элементов в БД (не всегда определено, т.к. может зависеть от объема свободной динамической памяти).

На абстрактном уровне БД представляет собой иерархическую структуру — дерево.

На физическом уровне БД реализуется связной схемой хранения. Располагаться БД может в статической или динамической памяти.