Интересная задача.

  • Автор темы Guest_
  • Дата начала
Статус
Закрыто для дальнейших ответов.
G

Guest_

#1
Задали интересную задачку.

Вот условие:
Найти вершины, через которые проходит наибольшее количество путей максимальной длины, и удалить их (правым удалением).
Входные данные
In.txt содержит последовательность чисел - ключей дерева.
Выходные данные
Out.txt содержит массив вершин, полученный прямым левым обходом итогового дерева.
Пример входных данных

10
11
8
7
9
6

Пример выходных данных
9


____________________________________________________________________
Составил алгоритм:

1. Обратный обход с расстановкой меток. Каждой вершине одна метка vh: высота дерева корнем которого является данная вершина.

Правила вычисления меток

vh = max {wh, uh} + 1, если v не лист;

vh = 0, если v - лист;

2. Во время этого же обхода находим вершины, для которых сумма меток сыновей максимальна. Эти вершины являются корнями путей максимальной длины.

3. Восстановим максимальный путь с корнем в найденной на шаге 3 вершине. Если r – корень некоторого пути максимальной длины, то необходимо сместиться из корня r в корни его левого и правого поддеревьев (если они существуют, то максимальный путь обязательно пройдет через них). Предположим, что v некоторая вершина максимального пути, тогда в качестве следующей вершины на этом пути надо взять корень того из поддеревьев вершины v, у которого высота больше. Если высоты поддеревьев у вершины v совпадают, то максимальный путь раздваивается: идет и в левое и в правое поддерево вершины v.

___________________________________________________________________

Я пытался что-то сделать
но не получилось реализовать процедуру расстановки меток
и поиска удаляемых элементов.
Вот что имеется:

Код:
#include <iostream>
#include <fstream>
using namespace std;

bool deleted=0;
int for_del;

class node //класс вершины дерева
{
public:
int value;
int descendants, altitude;
bool apt;
node *right, *left;

node(int k): value(k), descendants(1), altitude(0), right(0), left(0), apt(0) {};

~node()
{
delete right;
delete left;
};

friend ostream &operator<<(ostream &out, node *p)
{
out << p->altitude << endl;
if (p->left) out << p->left;
if (p->right) out << p->right;
return out;
};
};
//=================================================
class tree //класс дерева
{
int found;
public:
node *root;
tree(): root(0), found(0) {};
~tree() { delete root; };
//---------------------------------------
int add(int k)	//добавление
{
if (!root) 
{
root = new node(k);
return 1;
};
node *i = root, *pi = NULL;
while (i)
{
pi=i;
if (i->value == k) return 0;
if (k < i->value) i = i->left;
else i = i->right;
};
if (k < pi->value) pi->left = new node(k);
else pi->right = new node(k);
return 1;
};
//---------------------------------------
int remove(int k)
{
node *p = root,	*i = new node(0), *t, *tmp_root = i;
i->left = i->right = root;
while (p)
{
if (p->value == k) break;
i = p;
p = (p->value < k ? p->right : p->left);
};
if (!p) return 0;
if (!(p->left))
{
if (i->left == root) root = p->right;
else if (i->value < k) i->right = p->right;
else i->left = p->right;
}
else if (!(p->right))
{
if (i->right == root) root = p->left;
else if (i->value < k) i->right = p->left;
else i->left = p->left;
}
else 
{
t = p;
i = 0;
p = p->right;
while (p->left)
{
 i = p;
 p = p->left;
};
t->value = p->value;
if (i) i->left = p->right;
else t->right = p->right;
};
tmp_root->left = tmp_root->right = p->left = p->right = 0;
delete tmp_root;
delete p;
return 1; 
};
//---------------------------------------
int label_set(node *p)
{


У МЕНЯ ТУТ ПРОБЛЕМЫ


};




void find(node *p)
{

   
У МЕНЯ ТУТ ПРОБЛЕМЫ


friend ostream &operator<<(ostream &out, tree &t)
{
if (t.root) out << t.root;
return out;
};
};
//=================================================
tree t;

int main()
{
int k; //ввод из файла
ifstream fin("in.txt");
while (!fin.eof())
{
fin >> k;
t.add(k);
};
fin.close();

//что то типо этого???
if (t.label_set(t.root) 
t.find(t.root);
t.remove(for_del);


//3й обход: вывод

ofstream fout("out.txt"); //вывод в файл
fout << t;
fout.close();

return 0;
};

Может кто подскажет как написать те 2 процедурки чтобы все работало корректно?

Огромное спасибо!
daft@tut.by
 
Статус
Закрыто для дальнейших ответов.