Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 66, средняя оценка - 4.70
Deiron
25 / 25 / 1
Регистрация: 25.05.2009
Сообщений: 98
#1

Построение бинарного дерева из двумерного массива - C++

26.05.2009, 17:02. Просмотров 8361. Ответов 25
Метки нет (Все метки)

Стыдно, если честно, об этом просить, но "возник стопор" и путных идей не приходит.
Суть задачи:
Есть массив n*n состоящий из целых чисел. Надо создать бинарное дерево по следующему принципу:
значение индексного поля корня - всегда равно 0.
В 0 ряде выбирается два минимальных элемента (за исключением 0;0), меньший из которых становится левым (одно поле структуры будет равно номеру строки, второе самому элементу), другой правым.
Смотрим строку с номером, соответствующим номеру того столбца, в котором находился наш элемент (то есть, если в качестве левого мы взяли элемент массива, находившийся в столбце 3, то мы будем просматривать 3 строку). Там снова выбираем два минимальных элемента. Исключением будет элемент 3;0.
Далее, надо заполнять каждую из ветвей до тех пор, пока в поиске минимумов не останется только один элемент (столбцы, номера которых мы уже прошли из поиска минимумов исключаются), который становится листом.

Если говорить на примере, то из такой таблицы:
- 1 9 2
8 - 2 2
7 9 - 6
5 3 4 -

должно получиться следующее дерево (приведены значения индексных полей):
0
/ \
1 3
/ \ / \
2 3 2 1
| | | |
3 2 1 2
Нумерация строк и столбцов здесь естественно СИшная.
Буду очень благодарен, если поможете с этим делом.
Если кому-либо интересно, зачем мне это - сообщаю: для решения задачи коммивояжера "жадным" алгоритмом. Но в этой модификации алгоритма выбирается не один самый близкий город, а два наиболее близких.

Добавлено через 18 часов 27 минут 53 секунды
Как-то криво я задачу сформировал ((. Попробую по другому:
есть n городов. Стоимость перемещения из города в город - известна, причем стоимость перемещения из a в b может отличаться от стоимости перемещения из b в a. Нужно пройти все города и вернуться в 1й. Алгоритм нахождения минимального пути следующий:
ищем 2 города, путь до которых из данного города имеет минимальную стоимость.
Продолжаем искать такие города до тех пор, пока не будет сформирован путь по всем городам. (например, 1-2-3-4-5-1 или 1-3-5-2-6-4-1) В конечном итоге должно получится 2(n-1) путей из которых потом надо выбрать наименьший. Я планировал сделать это через бинарное дерево, однако пока не выходит ни одного нормального алгоритма.
Буду благодарен, если кто-нибудь сможет подсказать, каким образом можно решить эту задачу.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2009, 17:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Построение бинарного дерева из двумерного массива (C++):

Построение бинарного дерева на основе не бинарного - C++
В лабораторной работе есть такое задание: Создайте процедуру построения бинарного дерева на основе не бинарного. Объясните как вообще...

Построение бинарного дерева - C++
Доброй ночи! Пятые сутки не могу разобрать реализацию алгоритма на С++ Console Wizzard! Что такое бинарное дерево я знаю, даже разобрал...

Построение бинарного дерева - C++
Написать программу построения бинарного дерева с помощью связных структур и поиска в дереве при симметричном порядке обхода его. Если...

Построение бинарного дерева из строки - C++
Доброго времени суток, уважаемые. Хотел бы спросить у вас спросить совета относительно реализации следующей проблемы: Задано...

Построение бинарного дерева. Где ошибка? - C++
Насколько понял, tree->left, tree->right указывает на NULL. Почему, не могу разобратся. #include <iostream> #include <ctime> using...

Код Хаффмана реализованный через построение бинарного дерева - C++
Здравствуйте, есть код Хаффмана реализованный через построение бинарного дерева, узлами которого является элемент типа map ,либо символ и...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Evg
Эксперт CАвтор FAQ
17627 / 5851 / 376
Регистрация: 30.03.2009
Сообщений: 16,133
Записей в блоге: 26
30.05.2009, 18:07 #16
Это программа перевода выражения в так называемую польскую запись. С такой формой можно строить код по вычислению выражения, но неудобно "рисовать" дерево выражения (особенно в текстовом режиме). Хотя с него можно и рисовать, только код получается более геморройный, чем с дерева
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 18:16 #17
ну так если я введу выраженпие какоето, мне программа выдаст дерево?
Evg
Эксперт CАвтор FAQ
17627 / 5851 / 376
Регистрация: 30.03.2009
Сообщений: 16,133
Записей в блоге: 26
30.05.2009, 18:26 #18
нет. Если ты введёшь "(a+b)*(c-d)", то программа тебе выдаст "ab+cd-*" или что-то типа того. Чтобы выражение разрисовать в виде дерева в консоли, нужно мудохаться, потому как дерево за один проход нормально не распечатать.
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 18:47 #19
так а можно эту программу както оттредактировать чтоб она дерево выдавала?
Evg
Эксперт CАвтор FAQ
17627 / 5851 / 376
Регистрация: 30.03.2009
Сообщений: 16,133
Записей в блоге: 26
30.05.2009, 18:56 #20
Можно. Но долго, муторно и геморно
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 19:45 #21
а сколько это займет??мне бы до вт успеть(((а то отчислят(

#include <iostream>
#include <math.h>
#include "stack.h"
//------------------------------------------------------------------------------
typedef double(*pfun)(double);
struct Func{
char *name,shortname;
pfun fun; };
//------------------------------------------------------------------------------
double fnull(double x){return x;}
//------------------------------------------------------------------------------
const Func FTable[]={{"arcsin",'á',asin},
{"arccos",'â',acos},
{"arctg",'ã',atan},
{"sin",'ä',sin},
{"cos",'æ',cos},
{"tg",'ç',tan},
{"exp",'è',exp},
{"log",'ë',log},
{"abs",'ì',fabs},
{"",'ÿ',fnull}};
const int SizeFTable=sizeof(FTable)/sizeof(FTable[0]);
//------------------------------------------------------------------------------
class Node{
public:
virtual double calc()=0;
virtual void print()=0;
virtual ~Node(){}; };
//------------------------------------------------------------------------------
class NumNode: public Node{
const double num;
public:
NumNode(double NUM):num(NUM){};
double calc(){return num;}
void print(){std::cout<<num;} };
//------------------------------------------------------------------------------
class ParameterNode: public Node{
const char ch;
public:
ParameterNode(char CH):ch(CH){}
void print(){std::cout<<ch;}
double calc(){
std::cout<<ch<<"=";
double x; std::cin>>x; return x;} };
//------------------------------------------------------------------------------
class UnNode: public Node{
protected:
Node *child;
public:
UnNode(Node *CHILD):child(CHILD){}
~UnNode(){delete child;} };
//------------------------------------------------------------------------------
class UnMinusNode: public UnNode{
public:
UnMinusNode(Node *CHILD):UnNode(CHILD){}
double calc(){return -(child->calc());}
void print(){std::cout<<"-("; child->print(); std::cout<<")";}
};

Добавлено через 8 минут 18 секунд
//------------------------------------------------------------------------------
class UnFuncNode: public UnNode{
unsigned char fnum;
public:
UnFuncNode(char s,Node *CHILD):UnNode(CHILD){
int i=0; for(i=0; i<SizeFTable;++i){
fnum=i;
if(FTable[i].shortname==s){break;}
i=(i>=SizeFTable)?(SizeFTable-1):i;}}
double calc(){return (FTable[fnum].fun)(child->calc());}
void print(){std::cout<<FTable[fnum].name<<"("; child->print();
std::cout<<")";}
};
//------------------------------------------------------------------------------
class UnPlusNode: public UnNode{
public:
UnPlusNode(Node *CHILD):UnNode(CHILD){}
double calc(){return child->calc();}
void print(){child->print();}
};
//------------------------------------------------------------------------------
class BinNode: public Node{
protected:
Node *left,*right;
public:
BinNode(Node *LEFT,Node *RIGHT):left(LEFT),right(RIGHT){}
~BinNode(){delete left; delete right;} };
//------------------------------------------------------------------------------
class PlusNode: public BinNode{
public:
PlusNode(Node *LEFT,Node *RIGHT):BinNode(LEFT,RIGHT){}
double calc(){return left->calc()+right->calc();}
void print(){left->print(); std::cout<<"+("; right->print(); std::cout<<")";}
};
//------------------------------------------------------------------------------
class MinusNode: public BinNode{
public:
MinusNode(Node *LEFT,Node *RIGHT):BinNode(LEFT,RIGHT){}
double calc(){return left->calc()-right->calc();}
void print(){left->print(); std::cout<<"-("; right->print(); std::cout<<")";}
};
//------------------------------------------------------------------------------
class MultiplicationNode: public BinNode{
public:
MultiplicationNode(Node *LEFT,Node *RIGHT):BinNode(LEFT,RIGHT){}
double calc(){return left->calc()*right->calc();}
void print(){left->print(); std::cout<<"*("; right->print(); std::cout<<")";}
};




//------------------------------------------------------------------------------
class DivisionNode: public BinNode{
public:
DivisionNode(Node *LEFT,Node *RIGHT):BinNode(LEFT,RIGHT){}
double calc(){return left->calc()/right->calc();}
void print(){left->print(); std::cout<<"/("; right->print(); std::cout<<")";}
};
//------------------------------------------------------------------------------
class PowerNode: public BinNode{
public:
PowerNode(Node *LEFT,Node *RIGHT):BinNode(LEFT,RIGHT){}
double calc(){return pow(left->calc(),right->calc());}
void print(){left->print(); std::cout<<"^("; right->print(); std::cout<<")";}
};
//------------------------------------------------------------------------------
Node* postfixtree(const char *str){
Node *x1,*x2,*y;
int i=0;
stack <Node*> S;
while (str[i]!='\0'){
char ch=str[i];
switch(ch){
case '+': x2=S.pop(); x1=S.pop(); y=new PlusNode(x1,x2); break;
case '-': x2=S.pop(); x1=S.pop(); y=new MinusNode(x1,x2); break;
case '*': x2=S.pop(); x1=S.pop(); y=new MultiplicationNode(x1,x2); break;
case '/': x2=S.pop(); x1=S.pop(); y=new DivisionNode(x1,x2); break;
case '^': x2=S.pop(); x1=S.pop(); y=new PowerNode(x1,x2); break;
default : if((ch>=48)&&(ch<=57)){y=new NumNode(ch-48);}
else if(((ch>='a')&&(ch<='z'))||((ch>='A')&&(ch<='Z'))){y=new ParameterNode(ch);}
else{x1=S.pop(); y=new UnFuncNode(ch,x1);}}
S.push(y); ++i;} return S.pop();
}
//------------------------------------------------------------------------------
int main(int argc, char* argv[]){
Node *p1;
p1=postfixtree("AB+C*D-"); p1->print(); std::cout<<std::endl; double F=p1->calc();
std::cout<<"="<<F<<std::endl;
std::system("pause"); return 0;}

Добавлено через 36 секунд
// stack.h

#ifndef _STACK_
#define _STACK_

template <class T>
class stack{
T* datastore;
int first,maxsize;
public:
stack(unsigned int N=10):first(-1),maxsize(N){datastore=new T [N];}
~stack(){delete []datastore;}
T& top()const{return datastore[first];}
T pop(){return datastore[first--];}
void push(const T &X){
first++; if(first>=maxsize){int newsize=maxsize+1;
T* temp=new T[newsize];
for(int i=0;i<maxsize;++i){temp[i]=datastore[i];}
delete []datastore; datastore=temp;
maxsize=newsize;}
datastore[first]=X;}
};

#endif
Evg
Эксперт CАвтор FAQ
17627 / 5851 / 376
Регистрация: 30.03.2009
Сообщений: 16,133
Записей в блоге: 26
30.05.2009, 19:46 #22
Исходник какой-то неполный
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 19:46 #23
((((а чтож делать(*((((((
Evg
Эксперт CАвтор FAQ
17627 / 5851 / 376
Регистрация: 30.03.2009
Сообщений: 16,133
Записей в блоге: 26
30.05.2009, 19:56 #24
Блин, хоть исходники скопируй по человечески. Не поймёшь где начало а где конец
Используй BB-code

Если напишешь вот так, но внутри квадратных скобок удалишь пробелы

[ cpp ]
тут исходник
[ /cpp ]

то в форуме отобразится так

C++
1
тут исходник
Добавлено через 30 секунд
Цитата Сообщение от Олесенечек) Посмотреть сообщение
((((а чтож делать(*((((((
А ещё лучше засунь в архив и прикрепи к сообщению

Добавлено через 7 минут 58 секунд
Эта програ работает в обратную сторону по отношению к предыдущей. Т.е. польскую запись переводит в человеческую
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 20:23 #25
ну а можно из этих программ сделать то что надо в задаче??
Evg
Эксперт CАвтор FAQ
17627 / 5851 / 376
Регистрация: 30.03.2009
Сообщений: 16,133
Записей в блоге: 26
30.05.2009, 23:52 #26
Всё сводится к одному - напечатать дерево. И в этом кроется основной геморрой
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.05.2009, 23:52
Привет! Вот еще темы с ответами:

Варианты представления бинарного дерева с помощью массива и указателей - C++
1 - Варианты представления бинарного дерева с помощью массива. 2 - Варианты представления бинарного дерева с помощью указателей. ...

Запись массива в виде бинарного дерева и вывод его на экран! - C++
Задача: Зарандомить массив с 30 ел... от -100 до 100, создать бинарное дерево использую дан. массив, Вывод массива и дерева на экран.. ...

Запись бинарного дерева в файл и восстановление из него этого дерева - C++
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя - 1 указатель на структуру с данными, 2 и 3й указатель на...

Написать шаблон бинарного дерева с функцией распечатки дерева - C++
Не понимаю, что от меня хотят. Дано такое задание: Написать шаблон бинарного дерева с функцией распечатки дерева *(+(d,e),c) в виде...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
30.05.2009, 23:52
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru