Идеально-сбалансированные деревья

Цель: закрепление на практике знаний работы с бинарными деревьями. Построение идеально-сбалансированное дерева, реконструкция упорядоченного дерева в идеально-сбалансированное.

Методические рекомендации: лабораторная работа рассчитана на 2 часа и состоит из анализа одного разобранного задания и самостоятельной работы.

Необходимый уровень знаний:

• работа с указателями;

• работа со структурами;

• механизм рекурсии.

Задача

Построить упорядоченное бинарное дерево. Реконструировать дерево таким образом, чтобы дерево стало идеально-сбалансированным с сохранением упорядоченности.

#include <stdio.h>

#include <stdlib.h>

// вершина

typedef struct v_

{

// число в данной вершине

int x;

// указатели на: левого потомка, правого потомка, родителя

struct v_*L;

struct v_*R;

struct v_*P;

//int depth,diff;

} v;

// корень дерева

v*root = 0;

// количество элементов в массиве

int n;

// массив

int*a = 0;

// инициализация новой вершины

void newv(v*&V)

{

// выделение памяти

V = (v*)malloc(sizeof(v));

// обнуление всех указателей и числа в вершине

V->L = 0;

V->R = 0;

V->x = 0;

V->P = 0;

}

// печать отступа для вершины, расположенной на уровне h

void printspaces(int h)

{

if (h)

printf(" ");

for (int i=0; i<h-1; i++)

printf(" ");

}

// печать дерева

void printtree(v*V,int h,int lr)

{

if (V->R)

// рекурсивный вызов функции printtree() для правого потомка

printtree(V->R,h+1,1);

printspaces(h);

if (lr)

if (lr == 1)

printf("/->");

else

printf("\\->");

printf("%d",V->x);

printf("\n");

if (V->L)

// рекурсивный вызов функции printtree() для правого потомка

printtree(V->L,h+1,2);

}

// ввод массива с клавиатуры

void InputKeyboard()

{

printf("n = ");

scanf("%d",&n);

a = (int*)malloc(sizeof(int)*n);

for (int i=0; i<n; i++)

scanf("%d",&a[i]);

}

// добавить в массив поддерево с корнем V

void ToArray(v*V)

{

if (V->L) ToArray(V->L);

a[n] = V->x; n++;

if (V->R) ToArray(V->R);

}

// сформировать упорядоченный массив по упорядоченному бинарному дереву

void FormArrayByBT()

{

n = 0;

ToArray(root);

}

// занести в сбалансированное дерево числа из массива с номерами от i1 до i2 включительно

void Balanced(int i1,int i2,v*&V)

{

newv(V);

int i = (i1 + i2)/2;

V->x = a[i];

if (i1 <= i-1)

Balanced(i1,i-1,V->L);

if (i2 >= i+1)

Balanced(i+1,i2,V->R);

}

// сформировать сбалансированное дерево по упорядоченному массиву

void FormBalancedBTByArray()

{

Balanced(0,n-1,root);

}

void Print2()

{

if (root)

printtree(root,0,0);

else

printf("The BT is empty!\n");

}

void Menu()

{

int c;

do{

printf("\n Work with a binary tree (BT)\n");

printf("\nYou can...\n\n");

printf("1. Enter an array from keyboard.\n");

printf("2. Load an array from file.\n");

printf("3. Print the array.\n");

printf("4. Form an ideally balanced BT by array.\n");

printf("5. Print the BT.\n");

printf("0. Exit the program.\n");

printf("\nType 0-5 and press \"Enter\" ");

scanf("%d",&c);

switch (c)

{

case 1: InputKeyboard(); break;

case 2: InputFile(); break;

case 3: printarray(); break;

case 4: FormBalancedBTByArray(); break;

case 5: Print2(); break;

}

printf("OK\n");

}while (c != 0);

}

int main()

{

Menu();

return 0;

}

Самостоятельная работа.

Добавить в Задачу функцию обмена вершин с минимальным и максимальным значением.

Лабораторная работа №22

N-арные деревья

Цель: построение и вывод на экран N-арного дерева.

Методические рекомендации: лабораторная работа рассчитана на 2 часа и состоит из анализа одного разобранного задания и самостоятельной работы.

Необходимый уровень знаний:

• работа с указателями;

• работа со структурами;

• механизм рекурсии.

Задача

Построить и вывести на экран вершины n-арного дерева.

Дополнительное условие: исходные данные берутся из текстового файла.

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

Пример файла:

5 // корень

4 // первый потомок корня

-1 // -1 означает, что далее последуют числа, являющиеся потомками 4.

3 2

-2 // -2 - переход на уровень выше

4 // второй потомок корня

6 // третий потомок корня (4,4,6 - "братья")

#include <stdio.h>

#include <stdlib.h>

// вершина

typedef struct v_

{

int value;

// количество потомков

int nkids;

// указатель на родителя

struct v_*parent;

// указатель на первого потомка

struct v_*firstkid;

// указатель на "брата"

struct v_*next;

} v;

// корень дерева

v*root;

// создание новой вершины

void newv(v*&V)

{

// выделение памяти

V = (v*)malloc(sizeof(v));

// по умолчанию: родителя нет, потомков нет

V->parent = 0;

V->firstkid = 0;

V->next = 0;

V->nkids = 0;

}

// добавление нового потомка

v*newkid(v*parent,int x)

{

v*kid = parent->firstkid;

if (kid)

// переход к последнему на данный момент потомку родителя parent

while (kid->next)

kid = kid->next;

v*child;

newv(child);

// создание новой вершины со значением x

child->value = x;

// связывание созданной вершины с родителем

child->parent = parent;

parent->nkids++;

if (kid)

kid->next = child;

else

parent->firstkid = child;

return child;

}

// загрузка дерева из текстового файла

void Input()

{

FILE*f;

// открытие текстового файла на чтение

f = fopen("ntree.txt","r");

// сначала считывается корень

fscanf(f,"%d",&(root->value));

int x;

v*parent,*kid;

parent=root;

// пока не достигнут конец файла

while (fscanf(f,"%d",&x) != -1)

{

if (x >= 0)

// если из файла вводится новая вершина, то она добавляется

// потомком к родителю parent

kid = newkid(parent,x);

else

// текущий потомок становится текущим родителем

if (x == -1)

parent = kid;

// родитель текущего родителя становится текущим родителем

else

parent = parent->parent;

}

// закрытие файла

fclose(f);

}

//Первый способ печати:

// вывод дерева в одну строку

void printsimple(v*root)

//Дерево, указанное в примере, будет выглядеть так: 5 ( 4 ( 3 2 ) 4 6 )

{

printf(" %d ",root->value);

v*kid = root->firstkid;

if (kid)

{

printf("( ");

while (kid)

{

printsimple(kid);

kid = kid->next;

}

printf(")");

}

}

//Второй способ печати:

// печать отступа для вершины, находящейся на уровне h

void printspaces(int h)

{

printf(" ");

for (int i=0; i<h-1; i++)

printf(" ");

}

// печать вторым способом (вершины, находящиеся на одном уровне, выводятся на одной

// вертикали)

void printhoriz(v*root,int h,int isfirst)

/*

Дерево, указанное в примере, будет выглядеть так:

5 ----> 4 ----> 3

|

\-> 2

|

\-> 4

|

\-> 6

*/

{

// если уровень больше нуля и вершина - не первый потомок какого-то родителя, то

// делается отступ

if (h && !isfirst)

{

int i;

printspaces(h);

printf("|\n");

printspaces(h);

printf("\\->");

}

// печать значения

printf(" %2d ",root->value);

// если есть потомки, то для каждого из потомков осуществляются рекурсивные

// вызовы функции printhoriz()

if (root->nkids)

{

printf("---->");

v*kid = root->firstkid;

printhoriz(kid,h+1,1);

kid = kid->next;

while (kid)

{

printhoriz(kid,h+1,0);

kid = kid->next;

}

}

else

printf("\n");

}

intmain()

{

// создание корня дерева

newv(root);

// загрузка дерева из текстового файла

Input();

// вывод дерева на экран вторым способом

printhoriz(root,0,1);

return 0;

}

Самостоятельная работа.

Реализовать и вывести на экран 2-3 дерево.

Лабораторная работа №23

Графы

Цель: закрепление на практике работы со структурой типа граф. Создание графа в виде матрицы смежности и в виде списка смежных вершин. Инициализация. Обход вершин графа.

Методические рекомендации: лабораторная работа рассчитана на 2 часа и состоит из анализа двух разобранных заданий.

Для работы с графами предусмотрено 5 лабораторные работы и одно обязательное зачетное задание.

Необходимый уровень знаний:

• работа со списками;

• работа с матрицами;

• работа со структурами;

• механизм рекурсии.