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

Размещено на http://www.allbest.ru/

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

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



1. Постановка задачи

Разработать программный код для работы с бинарным деревом:

1. Обход дерева всеми способами (восходящий, нисходящий, последовательный).

2. Добавление вершины дерева.

3. Удаление вершины дерева.

4. Поиск вершины по ключу.

5. Уничтожение дерева.

6. Вывод дерева на экран.

7. Построить хорошо сбалансированное дерево.

8. Реализовать следующие способы вставки:

8.2. Построить дерево из N (N>0) вершин, в котором каждая внутренняя вершина имеет только одну дочернюю вершину, причем если значение вершины является нечетным, то она имеет левую дочернюю вершину, а если четным, то правую. Каждой создаваемой вершине присваивать очередное значение из исходного набора.

8.3. Построить дерево из N (N>0) вершин со следующей структурой: если вершина дерева является внутренней, то в случае, если она имеет нечетное значение, ее левая дочерняя вершина должна быть листом, а в случае, если она имеет четное значение, листом должна быть ее правая вершина. Для каждой внутренней вершины вначале создавать дочернюю вершину-лист, а затем дочернюю внутреннюю вершину (если данная вершина существует); каждой создаваемой вершине присваивать очередное значение из исходного набора.

2. Описание входных и выходных данных

Исходные данные:

Структура Node, играющая роль узла в бинарном дереве, содержит поля:

· date типа int для хранения значения вершины.

· leaf типа bool, являющаяся переменной, указывающей, является ли данная вершина листом или нет.

· Указатели *left и *right типа Node, для дочерних вершин.

Структура NodeInfo, созданная для хранения координат и информации о каждой вершине, для вывода его на экран, содержит следующие поля:

· x, y типа int для хранения координат вывода на PictureBox.

· *prev типа NodeInfo для указания на родительскую вершину. Используется для проведения ребра от дочернего элемента к родительскому элементу.

· *info типа Node, используется для получения значения вершины и вывода его на экран.

Используемые функции:

· void Insert1(int d) - стандартный способ добавления узла в дерево.

· void Insert2(int d) - способ добавления узла «змейкой».

· void Insert3(int d) - способ с обязательным добавлением листа в каждую вершину.

· void BalanceTree() - функция для хорошей балансировки дерева.

· void Delete(double d) - Функция удаления узла.

· void DestroyTree() - функция полного уничтожения дерева.

· int Height1() - подсчёт высоты дерева.

· int Nodes() - подсчёт узлов дерева.

· int Leafs() - подсчёт листьев дерева.

· void Inorder(vector<int> *Values) - последовательный обход дерева.

· void Preorder(vector<int> *Values) - нисходящий обход дерева.

· void Postorder(vector<int> *Values) - восходящий обход дерева.

· void Check(int x, int y, vector<NodeInfo*> *Base, int *WidthTree, int *HeightTree) - функция, предназначенная для вычисления координат для каждой вершины дерева, а также для сдвига ряда вершин в случае их пересечения.

Выходные данные:

Готовое сформированное, если был использован стандартный способ добавления вершин, бинарное дерево для вывода на экран.

3. Описание алгоритма

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

Способ балансировки дерева своеобразен. Используя последовательный обход дерева, вносим элементы дерева в векторный массив, а затем отправляем его в рекурсивную функцию, указывая в качестве параметров: адрес нового дерева, векторный массив, диапазон (начало и конец), середина массива. Рекурсивная функция, идя влево относительно индекса, делаем элемент перед индексом концом диапазона, а начало остаётся прежним. Складываем начало и конец и делим результат на два, получаем новый индекс, который попадет в дерево. Идя вправо, началом становится элемент, идущий после индекса, а конец остается прежний. Складываем конец с началом и прибавляем единицу, делим результат на два, получаем новый индекс и отправляем его в дерево. Эта процедура выполняется до тех пор, пока не будут выявленные все индексы для переноса в новое дерево. Старое дерево уничтожается.



4. Блок-схема программы



5. Кадры результатов тестирования

Окно программы без дерева в памяти.

Окно программы с выведенным бинарным деревом.

Окно программы с другим бинарным деревом.

Результат работы функции поиска узлов.

Пример другого бинарного дерева.

Пример балансировки приведённого выше дерева.

Способ вставки «Листья».



Способ вставки «Змейка».

6. Код программы

Пользовательские методы Form1:

void Join()

{

label3->Text = System::Convert::ToString(Height1());

label4->Text = System::Convert::ToString(Nodes());

label11->Text = System::Convert::ToString(Leafs());

label6->Text =""; label7->Text =""; label9->Text ="";

vector<int> Values;

Inorder(&Values);

for(unsigned int i = 0; i < Values.size(); i++)

label6->Text += System::Convert::ToString(Values[i]) + " ";

Values.clear();

Preorder(&Values);

for(unsigned int i = 0; i < Values.size(); i++)

label7->Text += System::Convert::ToString(Values[i]) + " ";

Values.clear();

Postorder(&Values);

for(unsigned int i = 0; i < Values.size(); i++)

label9->Text += System::Convert::ToString(Values[i]) + " ";

Values.clear();

} программный код бинарный дерево

void Paint(bool search)

{

Graphics ^ Графика = pictureBox1->CreateGraphics();

Pen ^ Чёрное_Перо = gcnew Pen(Color::Black);

Pen ^ Серое_Перо = gcnew Pen(Color::Gray);

Brush ^ Кисть = gcnew SolidBrush(Color::Red);

Графика->Clear(SystemColors::Control);

vector<NodeInfo*> Base;

int Width = this->pictureBox1->Width;

int Height = this->pictureBox1->Height;

int x = pictureBox1->Size.Width / 2 - 15, y = 10;

int WidthTree, HeightTree; Check(x, y, &Base, &WidthTree, &HeightTree);

//textBox2->Text = WidthTree + " " + HeightTree;

if(WidthTree >= pictureBox1->Width)

{ this->Width += WidthTree - pictureBox1->Width ; this->pictureBox1->Width = WidthTree + 50; }

if(HeightTree >= pictureBox1->Height)

{ this->Height += HeightTree - pictureBox1->Height ; this->pictureBox1->Height = HeightTree + 50; }

for(unsigned int index = 0; index < (Base).size(); index++)

{

Графика->DrawEllipse(Чёрное_Перо, (Base)[index]->x, (Base)[index]->y, 25, 25);

Графика->DrawString(System::Convert::ToString((Base)[index]->info->data), Font, Кисть, (float)(Base)[index]->x + 4, (float)(Base)[index]->y + 6);

if((Base)[index]->prev != 0 && (Base)[index]->prev != 0)

Графика->DrawLine(Серое_Перо, (Base)[index]->x + 13, (Base)[index]->y, (Base)[index]->prev->x + 13, (Base)[index]->prev->y + 26);

}

if(search)

{

int i = 0, j = 0, k = 0, value; textBox1->Text += " ";

for(i = 0; i < textBox1->Text->Length; i++)

if(textBox1->Text[i] != ' ')

{

k = i; while(textBox1->Text[k] != ' ') { j++; k++; }

value = System::Convert::ToInt32(textBox1->Text->Substring(i, j));

for(unsigned int index = 0; index < (Base).size(); index++)

{

if(value == (Base)[index]->info->data)

{

Brush ^ Заливка = gcnew SolidBrush(Color::Green);

Графика->FillEllipse(Заливка, (Base)[index]->x, (Base)[index]->y, 25, 25);

Графика->DrawString(System::Convert::ToString((Base)[index]->info->data),

Font, Кисть, (float)(Base)[index]->x + 4, (float)(Base)[index]->y + 6);

}

}

i = k; j = 0;

}

}

}

#pragma endregion

private: System::Void button3_Click(System::Object^ sender, System::EventArgs^ e) {

Paint(false); textBox2->Text = "Нарисовано";

}

private: System::Void Form1_Load(System::Object^ sender, System::EventArgs^ e) {

button2->Enabled = false; button3->Enabled = false;

button4->Enabled = false; button5->Enabled = false;

button6->Enabled = false;

private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {

int i = 0, j = 0, k = 0; textBox1->Text += " ";

for(i = 0; i < textBox1->Text->Length; i++)

if(textBox1->Text[i] != ' ')

{

k = i; while(textBox1->Text[k] != ' ') { j++; k++; }

if(radioButton1->Checked)

Insert1(System::Convert::ToInt32(textBox1->Text->Substring(i, j)));

else if(radioButton2->Checked)

Insert2(System::Convert::ToInt32(textBox1->Text->Substring(i, j)));

else if(radioButton3->Checked)

Insert3(System::Convert::ToInt32(textBox1->Text->Substring(i, j)));

else if(radioButton4->Checked) {

Insert1(System::Convert::ToInt32(textBox1->Text->Substring(i, j)));

BalanceTree(); }

i = k; j = 0;

}

button2->Enabled = true; button3->Enabled = true;

button4->Enabled = true; button5->Enabled = true;

button6->Enabled = true;

textBox2->Text = "Добавлено"; Join();

}

private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e) {

DestroyTree();

label3->Text = "0"; label4->Text = "0"; label11->Text = "0";

pictureBox1->BackColor = SystemColors::Control;

button2->Enabled = false; button3->Enabled = false;

button4->Enabled = false; button5->Enabled = false;

button6->Enabled = false;

label6->Text ="None"; label7->Text ="None"; label9->Text ="None";

this->pictureBox1->Width = 350; this->Width = 678;

this->pictureBox1->Height = 330; this->Height = 380;

textBox2->Text = "Уничтожено";

}

private: System::Void button4_Click(System::Object^ sender, System::EventArgs^ e) {

double value = System::Convert::ToInt32(textBox1->Text);

Delete(value); Join(); textBox2->Text = "Удалено";

}

private: System::Void button5_Click(System::Object^ sender, System::EventArgs^ e) {

Paint(true); textBox2->Text = "Найдено";

}

private: System::Void button6_Click(System::Object^ sender, System::EventArgs^ e) {

BalanceTree(); Join(); textBox2->Text = "Сбалансировано";

}

};

}

Файл InfoTree.h

#pragma once

#include <vector>

#include <string>

using namespace std;

struct Node

{

int data; bool leaf; Node *left, *right;

Node(int value, bool IsLeaf = false): data(value),

left(NULL), right(NULL), leaf(IsLeaf) {}

};

struct NodeInfo

{

int x, y;

NodeInfo *prev;

Node *info;

};

void Insert1(int d);

void Insert2(int d);

void Insert3(int d);

void BalanceTree();

void Delete(double d);

void DestroyTree();

int Height1();

int Nodes();

int Leafs();

void Inorder(vector<int> *Values);

void Preorder(vector<int> *Values);

void Postorder(vector<int> *Values);

void Check(int x, int y, vector<NodeInfo*> *Base, int *WidthTree, int *HeightTree);

Файл MainInfo.cpp

#pragma once

#include "stdafx.h"

#include "InfoTree.h"

#define NULL 0

Node *root = NULL;

int Max(int x, int y)

{ return (x > y) ? x : y; }

void Insert1(Node **n, int d)

{

if(*n == NULL) *n = new Node(d);

else

{

if((*n)->data == d) return;

else if((*n)->data > d) Insert1(&(*n)->left, d);

else Insert1(&(*n)->right, d);

}

}

void Insert2(Node **n, int d)

{

if(*n == NULL) *n = new Node(d);

else

{

if((*n)->data == d) return;

else if((*n)->data % 2 != 0) Insert2(&(*n)->left, d);

else Insert2(&(*n)->right, d);

}

}

bool Insert3(Node **n, int d, bool IsLeaf)

{

if(*n == NULL) { *n = new Node(d, IsLeaf); return true; }

else if((*n)->data != d)

{

if((*n)->data % 2 != 0 && !(*n)->leaf)

{

bool temp = Insert3(&(*n)->left, d, true);

if(!temp) Insert3(&(*n)->right, d, false);

return true;

}

else if((*n)->data % 2 == 0 && !(*n)->leaf)

{

bool temp = Insert3(&(*n)->right, d, true);

if(!temp) Insert3(&(*n)->left, d, false);

return true;

}

}

return false;

}

/* 1 - left 2 - right */

void DeleteNode(Node *n, Node *previous, double value, int way)

{

if(n != NULL)

if((n)->data == value && (n)->data != root->data)

{

Node *Temp1, *Temp3;

if((n)->right == NULL && (n)->left == NULL)

{

switch(way) {

case 1: { (previous)->left = NULL; break; }

case 2: { (previous)->right = NULL; break; } }

}

else if((n)->right != NULL && (n)->left != NULL)

{

Temp1 = (n)->left;

Temp3 = (n)->right;

(Temp3)->left = NULL;

switch(way) {

case 1: { (previous)->left = Temp1; break; }

case 2: { (previous)->right = Temp1; break; } }

Temp3 = Temp1;

while((Temp3)->right != NULL)

Temp3 = (Temp3)->right;

(Temp3)->right = (n)->right;

}

else if((n)->right != NULL || (n)->left != NULL)

{

if((n)->right != NULL)

Temp1 = (n)->right;

else Temp1 = (n)->left;

switch(way) {

case 1: { (previous)->left = Temp1; break; }

case 2: { (previous)->right = Temp1; break; } }

}

delete n;

}

else

{

DeleteNode((n)->left, n, value, 1);

DeleteNode((n)->right, n, value, 2);

}

}

void DestroyTree(Node **n)

{

if(*n != NULL)

{

DestroyTree(&(*n)->left);

DestroyTree(&(*n)->right);

(*n)->left = NULL;

(*n)->right = NULL;

delete *n;

}

}

int Height(Node *n)

{

if(!n) return 0;

else return 1 + Max(Height(n->left), Height(n->right));

}

int Nodes(Node *n)

{

if(!n) return 0;

else return 1 + Nodes(n->left) + Nodes(n->right);

}

int Leafs(Node *n)

{

if(!n) return 0;

else if(n->left == NULL && n->right == NULL) return 1;

else return Leafs(n->left) + Leafs(n->right);

}

void Inorder(Node *n, vector<int> *info)

{

if(n)

{

Inorder(n->left, info);

info->push_back(n->data);

Inorder(n->right, info);

}

}

void Preorder(Node *n, vector<int> *info)

{

if(n)

{

info->push_back(n->data);

Preorder(n->left, info);

Preorder(n->right, info);

}

}

void Postorder(Node *n, vector<int> *info)

{

if(n)

{

Postorder(n->left, info);

Postorder(n->right, info);

info->push_back(n->data);

}

}

void MakeBalanceTree(int Size, Node **n, vector<int> *info, int begin, int end, int index)

{

Node *Current = *n;

int SizeLeft, SizeRight;

if(Size == 0) *n = NULL;

else

{

SizeLeft = Size / 2; SizeRight = Size - SizeLeft - 0;

Current = new Node((*info)[index]);

if((*info)[(index + begin) / 2] < (*info)[index]) MakeBalanceTree(SizeLeft, &(Current->left), info, begin, index - 1, (index + begin) / 2);

if((*info)[(index + 1 + end) / 2] > (*info)[index]) MakeBalanceTree(SizeRight, &(Current->right), info, index + 1, end, (index + 1 + end) / 2);

*n = Current;

}

}

// - Методы вызовов

void BalanceTree()

{

vector<int> info;

Inorder(root, &info);

int size = Nodes(root);

Node *NewRoot; MakeBalanceTree(size, &NewRoot, &info, 0, info.size() - 1, info.size() / 2);

DestroyTree(); root = NewRoot;

info.clear();

}

void Insert1(int value)

{ Insert1(&root, value); }

void Insert2(int value)

{ Insert2(&root, value); }

void Insert3(int value)

{ Insert3(&root, value, false); }

void Delete(double value)

{ DeleteNode(root, NULL, value, 0); }

int Nodes() { return Nodes(root); }

int Height1() { return Height(root); }

int Leafs() { return Leafs(root); }

void DestroyTree()

{ DestroyTree(&root); root = NULL; }

void Inorder(vector<int> *Values)

{ Inorder(root, Values); }

void Preorder(vector<int> *Values)

{ Preorder(root, Values); }

void Postorder(vector<int> *Values)

{ Postorder(root, Values); }

void Walk(Node *n, NodeInfo *prev, int x, int y, vector<NodeInfo*> *Base)

{

if(n)

{

NodeInfo *temp = new NodeInfo;

temp->info = n;

temp->x = x;

temp->y = y;

temp->prev = prev;

Base->push_back(temp);

Walk(n->left, temp, x - 25, y + 35, Base);

Walk(n->right, temp, x + 25, y + 35, Base);

}

}

void Sort(vector<NodeInfo*> *Base)

{

for(unsigned int i = 0; i < Base->size() - 1 ; i++)

{

for(unsigned int j = i + 1; j < Base->size(); j++)

{

if((*Base)[i]->x == (*Base)[j]->x && (*Base)[i]->y == (*Base)[j]->y)

{

for(int k = j - 1; k < Base->size(); k++) (*Base)[k]->x += 50;

NodeInfo *Temp = (*Base)[j - 1]->prev; int n = 25;

while(Temp->prev != NULL) { Temp->x += n; n /= 2; Temp = Temp->prev; }

(*Base)[0]->x += 25;

}

}

}

}

void WidthAndHeight(vector<NodeInfo*> *Base, int *WidthTree, int *HeightTree)

{

int MinX = (*Base)[0]->x, MaxX = (*Base)[0]->x,

MinY = (*Base)[0]->y, MaxY = (*Base)[0]->y;

for(unsigned int i = 0; i < Base->size(); i++)

{

if(MinX >= (*Base)[i]->x) MinX = (*Base)[i]->x;

if(MaxX <= (*Base)[i]->x) MaxX = (*Base)[i]->x;

if(MinY >= (*Base)[i]->y) MinY = (*Base)[i]->y;

if(MaxY <= (*Base)[i]->y) MaxY = (*Base)[i]->y;

}

*WidthTree = MaxX - MinX + 25; *HeightTree = MaxY - MinY + 25;

for(unsigned int i = 0; i < Base->size(); i++)

(*Base)[i]->x -= *WidthTree / 2 - 350 /3;

}

void Check(int x, int y, vector<NodeInfo*> *Base, int *WidthTree, int *HeightTree)

{

Walk(root, NULL, x, y, Base); Sort(Base);

WidthAndHeight(Base, WidthTree, HeightTree);

}

/*

Набор тестов

65 21 47 85 20 36 14 58 45 96 32 58 49 14 64

65 32 14 58 72 34 85 27 19 37 28 35 24 10 70

19 37 28 64 75 95 32 18 29 35 72 96 11 74 82

34 85 21 26 35 74 29 28 24 25 77 55 63 30 20

75 95 15 35 85 45 25 65 94 76 34 16 82 46 55

45 32 10 15 78 52 16 90 47 82 39 17 19 37 80

50 35 40 45 43 42 44 60 70 80 75

*/

Размещено на Allbest.ru