Лабораторная работа № 13. Разработка проекта с использованием бинарных деревьев Проект с использованием бинарного дерева состоит из трех частей.
Задание
Краткие теоретические сведения
1. В правой части записана главная функция проекта и функции, выполняющие некоторые действия с данными.
Дополнить комментарии к программе.
#include "stdafx.h"
#include <locale>
#include "tree.h"
#include <fstream>
using namespace std;
#define NN 100000
#define N 3
struct NodeTree
{ int key; };
btree::CMP cmpfnc(void* x, void* y)
{ btree::CMP rc = btree::EQUAL;
if (((NodeTree*)x)->key < ((NodeTree*)y)->key) rc = btree::LESS;
else
if (((NodeTree*)x)->key > ((NodeTree*)y)->key) rc = btree::GREAT;
return rc;
}
void Print(void* x)// вывод при обходе
{ cout <<((NodeTree*)x)->key <<ends;}
// построение дерева из файла
bool BuildTree(char *FileName, btree::Object& tree)
{ bool rc=true;
FILE *inFile = fopen(FileName, "r");
if (inFile == NULL)
{ cout<<"Ошибка открытия входного файла"<<endl;
rc = false; }
// Заполнение дерева и вывод исходных данных
cout<<" Исходные данные"<< endl;
while (!feof(inFile))
{ int num; fscanf(inFile, "%d", &num,1);
NodeTree *a = new NodeTree();
a->key=num; tree.Insert(a);
cout<<num<<endl; }
fclose(inFile);
return rc;
}
FILE * outFile;
// функция записи одного элемента в файл
void SaveToFile(void *x)
{ NodeTree *a = (NodeTree*)x;
int q = a->key;
fprintf(outFile, "%d\n", q);
}
// сохранение в файл заданного дерева сверху вниз
void SaveTree(btree::Object &tree, char *FileName)
{ outFile = fopen(FileName, "w");
if (outFile == NULL)
{ cout<<"Ошибка открытия выходного файла"<<endl;
return; }
tree.Root->ScanDown(SaveToFile);
fclose (outFile);
}
int _tmain(int argc, _TCHAR* argv[])
{setlocale (LC_CTYPE, "Russian");
btree::Object t1=btree::Create(cmpfnc);;
int choise; NodeTree a1 = {1},
a2 = {2}, a3 = {3}, a4 = {4}, a5 = {5}, a6 = {6};
bool rc = t1.Insert(&a4);//true 4
rc = t1.Insert(&a1);//true 1
rc = t1.Insert(&a6);//true6
rc = t1.Insert(&a2);//true 2
rc = t1.Insert(&a3);//true 3
rc = t1.Insert(&a5);//true 5
int k; for(;;) { cout<<"Меню:"<<endl;
cout<<"1 - вывод дерева на экран"<<endl;
cout<<"2 - добавление элемента"<<endl;
cout<<"3 - удаление элемента"<<endl;
cout<<"4 - сохранить в файл"<<endl;
cout<<"5 - загрузить из файла"<<endl;
cout<<"6 - очистить дерево"<<endl;
cout<<"0 - выход"<<endl;
cout<<"сделайте выбор"<<endl; cin>>choise; switch(choise){
case 0: exit(0);
case 2: { NodeTree *a = new NodeTree;
cout<<"введите ключ"<<endl; cin>>k;
a->key=k; t1.Insert(a); } break;
case 1: if (t1.Root) t1.Root->ScanByLevel(Print);
else cout<<"Дерево пустое"<<endl; break;
case 3: {NodeTree *c = new NodeTree;
cout<<"введите ключ"<<endl; cin>>k;
c->key=k; t1.Delete(c); } break;
case 4: SaveTree(t1, "G.txt"); break;
case 5: BuildTree("G.txt", t1); break;
case 6: { while (t1.Root) t1.Delete(t1.Root); } break; }
}
return 0;
}
2. В правой части записан программный модуль Tree.cpp.
Написать комментарии к программному коду.
Программный модуль Tree.cpp
#include "stdafx.h"
#include "Tree.h"
namespace btree {// бинарное дерево, не доп. дублирование ключей
{ Object Create(CMP (*f)(void*, void*))
{ return *(new Object(f));
}
Node* Node::Min()
{ Node* rc = this; if (rc->Left!= NULL)
rc = rc->Left->Min();
return rc;
}
Node* Node::Next()
{ Node* rc = this, *x = this;
if (rc->Right!= NULL) rc = rc->Right->Min();
else { rc = this->Parent;
while (rc!= NULL && x == rc->Right)
{ x = rc; rc = rc->Parent; } }
return rc;
}
void Node::ScanDown(void (*f)(void* n))
{ f(this->Data); cout<<endl;
if (this->Left!= NULL)
this->Left->ScanDown(f);
if (this->Right!= NULL)
this->Right->ScanDown(f);
}
Node* Object::Search(void* d, Node* n)
{Node* rc = n;
if (rc!= NULL) { if (isLess(d, n->Data))
rc = Search(d,n->Left);
else if (isGreat(d, n->Data))
rc = Search(d,n->Right); }
return rc;
}
bool Object::Insert(void* d)
{ Node* x = this->Root, *n = NULL;
bool rc = true;
while (rc == true && x!= NULL)
{ n = x; if (isLess(d,x->Data)) x = x->Left;
else if (isGreat(d,x->Data)) x = x->Right;
else rc = false; }
if (rc == true && n == NULL)
this->Root=new Node(NULL, NULL, NULL, d);
else if (rc == true && isLess(d, n->Data))
n->Left = new Node(n, NULL, NULL, d);
else if (rc == true && isGreat(d, n->Data))
n->Right = new Node(n, NULL, NULL, d);
return rc;
};
bool Object::Delete(Node* n)
{ bool rc = true;
if (rc = (n!= NULL))
{ if (n->Left == NULL && n->Right== NULL)
{ if (n->Parent == NULL)
this->Root = NULL;
else if (n->Parent->Left == n)
n->Parent->Left = NULL;
else n->Parent->Right = NULL;
delete n; }
else if (n->Left==NULL && n->Right!=NULL)
{ if (n->Parent == NULL)
this->Root = n->Right;
else if (n->Parent->Left == n)
n->Parent->Left = n->Right;
else n->Parent->Right = n->Right;
n->Right->Parent = n->Parent; delete n; }
else if (n->Left!=NULL && n->Right==NULL)
{if (n->Parent == NULL)
this->Root = n->Left;
else if (n->Parent->Right == n)
n->Parent->Left = n->Left;
else n->Parent->Right = n->Left;
n->Left->Parent = n->Parent;
delete n; }
else if (n->Left!=NULL && n->Right!= NULL)
{ Node* x = n->Next();
n->Data = x->Data; rc = Delete(x); } }
return rc;
}
void Node::ScanLevel(void (*f)(void* n), int i)//вывести вершины уровня
{ if (this->Left!= NULL)
this->Left->ScanLevel(f,i);
if(this->GetLevel()==i)f(this->Data);
if (this->Right!= NULL)
this->Right->ScanLevel(f,i);
}
int Node::GetLevel()
{ Node *rc=this; int q=0;
while(rc->Parent!= NULL)
{rc=rc->Parent; q++;}
return q;
};
void Node::ScanByLevel(void (*f)(void* n))
{ for(int i=0;i<10;i++){
std::cout<<'\t';
this->ScanLevel(f,i);
std::cout<<'\n'; }
};
}
3. В правой части записан заголовочный файл Tree.h.
Написать комментарии к программному коду.
Заголовочный файлTree.h
#include <iostream>
namespace btree
{ enum CMP{LESS = -1,EQUAL = 0,
GREAT = 1};
struct Node// узел бинарного списка
{ Node* Parent;// указатель на родителя
Node* Left;// указатель на левую ветвь
Node* Right;// указатель на правую ветвь
void* Data;// данные
Node(Node* p, Node* l, Node* r, void* d)// конст-р
{ Parent = p; Left = l; Right = r; Data = d; }
Node* Next();// следующий по ключу
Node* Prev();// предыдущий по ключу
Node* Min();// минимум в поддереве
Node* Max();// максимум в поддереве
void ScanDown(void (*f)(void* n));// обход поддерева сверху вниз
void Scan(int (*f)(void* n));
void ScanLevel(void (*f)(void* n), int);
int GetLevel();
void ScanByLevel(void (*f)(void* n)); };
struct Object// интерфейс бинарного дерева
{ Node* Root;// указатель на корень
CMP (*Compare)(void*, void*);// функция сравнения
Object(CMP (*f)(void*, void*))
{ Root = NULL; Compare = f; };
Node* Max(){return Root->Max();};
Node* Min(){return Root->Min();};
bool isLess(void* x1, void* x2)
const{return Compare(x1, x2) == LESS;};
bool isGreat(void* x1, void* x2)
const{return Compare(x1, x2) == GREAT;};
bool isEqual(void* x1, void* x2)
const{return Compare(x1, x2) == EQUAL;};
bool Insert(void* data);// добавить элемент
Node* Search(void* d, Node* n);// найти по ключу
Node* Search(void* d){return Search(d, Root);};
bool Delete(Node* e);// удалить по адресу элемента
bool Delete(void* data){return Delete(Search(data));};// удалить по ключу
void ScanDown(void (*f)(void* n))
{Root->ScanDown(f);};// обход дерева
btree::Object BuildTree(char *);
void SaveToFile(void *);
void SaveTree(btree::Object tree, char *);
};
Object Create(CMP (*f)(void*, void*));// создать бинарное дерево };
4. Добавить к проекту функции смешанного и нисходящего обхода дерева с выводом на консоль, проверки сбалансированности дерева и функцию в соответствии с вариантом из таблицы, представленной в лабораторной работе № 12, изменив ее так, чтобы функция соответствовала проекту лабораторной работы № 13.
В начало практикума
Дата публикования: 2015-02-18 ; Прочитано: 472 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
studopedia.org - Студопедия.Орг - 2014-2025 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования
(0.132 с) ... 
