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

Стыдно, если честно, об этом просить, но "возник стопор" и путных идей не приходит.
Суть задачи:
Есть массив 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) путей из которых потом надо выбрать наименьший. Я планировал сделать это через бинарное дерево, однако пока не выходит ни одного нормального алгоритма.
Буду благодарен, если кто-нибудь сможет подсказать, каким образом можно решить эту задачу.

0

а сколько это займет??мне бы до вт успеть(((а то отчислят(

#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

0

Исходник какой-то неполный

0

((((а чтож делать(*((((((

0

Блин, хоть исходники скопируй по человечески. Не поймёшь где начало а где конец
Используй BB-code

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

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

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

Добавлено через 30 секунд

Сообщение от Олесенечек) ((((а чтож делать(*((((((

А ещё лучше засунь в архив и прикрепи к сообщению

Добавлено через 7 минут 58 секунд
Эта програ работает в обратную сторону по отношению к предыдущей. Т.е. польскую запись переводит в человеческую

0

ну а можно из этих программ сделать то что надо в задаче??

0

Всё сводится к одному - напечатать дерево. И в этом кроется основной геморрой

0