Белорусский государственный университет
информатики и радиоэлектроники
Факультет заочного обучения
Кафедра высшей математики
Контрольная работа
по дисциплине
КПиЯП
студента 2-го курса группы 900502
Микулича Алексея Алексеевича
Вариант 6
Минск 2010
Задача 1
Используя классы создать бинарное дерево. В узлах бинарного дерева имеется элемент (целое число), определяющий частоту обращения к узлу. В записях дерева хранится фамилия, имя, отчество, адрес, место работы, должность, дата рождения. Элементы дерева заполнять из файла. Реализовать функцию, которая создаст новое бинарное дерево. В качестве ключа использовать частоту обращения к узлу дерева. Путь к узлам дерева должен быть оптимальным (наикратчайшим). Записи из старого дерева в новое не перемещать. Рекурсии и библиотечные функции не использовать. В дереве не более 30 узлов. Частоты в узлах дерева не совпадают. Исходное и результирующее дерево вывести на экран.
Код программы:
Формирование дерева из файла и обход:
n»ї #include "stdafx.h"
#include <iostream>
#include <string>
#include <fstream>
typedef unsigned short uShort;
using namespace std;
struct tItem //treeItem
{
int cData; //childData
tItem* lChild; //leftChild
tItem* rChild; //rightChild
};
tItem* tRoot; //treeRoot
void initTree()
{
tRoot = new tItem();
tRoot->lChild = NULL;
tRoot->rChild = NULL;
}
ifstream iFile; //input file var
struct retChild //return R
{
bool sFilled; //is record filled
uShort direction; //direction
uShort level; //is brunch the last
int cData; //child data
};
retChild loadTree( tItem* tTree, uShort lvl )
{
retChild res;
if( iFile.good() )
{
iFile >> res.direction >> res.level >> res.cData;
res.sFilled=true;
}else
{
res.sFilled=false;
}
while( res.sFilled )
{
if( res.level > lvl )
{
tItem* tmp;
tmp = new tItem();
tmp->lChild = NULL;
tmp->rChild = NULL;
tmp->cData = res.cData;
if( res.direction == 0 )
{
tTree->lChild = tmp;
}else
{
tTree->rChild = tmp;
}
res = loadTree( tmp, res.level );
}else
{
break;
}
}
return res;
}
void printTree( tItem* item, uShort lvl ) //item = tree item, lvl = level
{
if( item != NULL )
{
string tmp;
tmp.clear();
for( int i = 1; i < lvl; i++ )
tmp += '-';
cout << tmp << item->cData << "\n";
printTree( item->lChild, lvl+1 );
printTree( item->rChild, lvl+1 );
}
}
void bTree(tItem *dr)
{
struct stek
{
tItem *d;
stek *s;
} *st,*st1=NULL;
tItem *dr1;
dr1=dr;
int pr=1,i=0;
for(i=0;i<2;i++)
{
st=(stek*)calloc(1,sizeof(stek));
st->d=dr1;
st->s=st1;
st1=st;
}
printf("%d vstrech\n",dr1->cData);
while(st)
{
do
{
if(pr && dr1->lChild) dr1=dr1->lChild;
else if(dr1->rChild) dr1=dr1->rChild;
pr=1;
if(dr1->lChild && dr1->rChild)
{
st=(stek*)malloc(sizeof(stek));
st->d=dr1;
st->s=st1;
st1=st;
}
printf("%d vstrech\n",dr1->cData);
} while(dr1->lChild || dr1->rChild);
dr1=st->d;
st1=st->s;
free(st);
st=st1;
if(dr1->rChild) pr=0;
}
}
int main()
{
initTree();
iFile.open( "tree.in" );
uShort level;
uShort cData;
iFile >> level >> cData;
tRoot->cData = cData;
loadTree( tRoot, level );
iFile.close();
printTree( tRoot, 1 );
bTree( tRoot);
return 0;
}