Бинарное Поисковое Дерево

[Maestresa]

Помогите пожалуйста решить задачу.
Условие
Найти такой путь максимальной длины между вершинами дерева, у которого сумма ключей конечных вершин минимальна. Удалить (правым удалением) корневую вершину этого пути.

Входные данные
in.txt содержит последовательность чисел — ключей дерева.

Выходные данные
out.txt содержит массив вершин, полученный прямым левым обходом итогового дерева.

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
int el;
struct Tree {
int key;
Tree* left;
Tree* right;
int high;
int sum;
int length;
};
int High(Tree* T)
{
int a = 1, b = 0, c;
if (T == NULL)
return 0;
c = High(T->left);
if (c > b)
b = c;
c = High(T->right);
if (c >b)
b = c;
return a + b;
}
void push(int a, Tree** t) {
if (!*t) {
(*t) = new Tree;
(*t)->key = a;
(*t)->left = NULL;
(*t)->right = NULL;}
else
if (a > (*t)->key) {
if ((*t)->right) {
if ((*t)->right->key != a)
{
push(a, &(*t)->right);}
}		else
{	push(a, &(*t)->right);}
}else {
if ((*t)->left) {
if ((*t)->left->key != a)
{push(a, &(*t)->left);
}
}else 
{push(a, &(*t)->left);
}
}
}

void find_max_length(Tree* t){

if(t){
find_max_length(t->left);
find_max_length(t->right);


t->high=High(t)-1;
cout<<t->high<<" ";//высоты
if (t->right && t->left){
t->length=t->left->high+t->right->high+2;
}
else{
if (t->right) {
t->length=(t->right->high)+1;

}else{
if(t->left){t->length=(t->left->high)+1;
}
else
t->length=0;

}
}
cout<<t->length<<endl;
}}

void print(Tree* t) {
if (t) 
{
cout << t->key<< endl;
print(t->left);
print(t->right);
}
}

int main () { 
Tree* tree = NULL;
int n = 0;
int s = 0;
ifstream in;
in.open("input.txt");

while(in) {
in >> s;
push(s, &tree);
}
vector<Tree> A;
print(tree);
find_max_length(tree);
system("pause");
return 0; 
}

вот нашла высоты всех узлов, нашла максимальные длины путей, проходящих через каждый узел и зашла в тупик: как же теперь разобраться с минимальной суммой конечных вершин?
в задаче есть ограничение на количество обходов дерева(не больше двух без учета построния)
может у кого есть идеи что же тут дальше делать?

 

[rrrFer]

Не понятно как этот код с задачей связан. Это раз.
Не понятна задача. Это два.
Не понятно как условие задачи связано с "выходные данные". Это три.

Найти такой путь максимальной длины между вершинами дерева, у которого сумма ключей конечных вершин минимальна. Удалить (правым удалением) корневую вершину этого пути.

Выходные данные
out.txt содержит массив вершин, полученный прямым левым обходом итогового дерева.

Путь максимальной длины - это одно - тебе надо просто найти 2 наиболее глубоких вершины.
Сумма ключей минимальная - это совсем другое. Как так, "максимальной длины, у которого сумма минимальна" - не понятно. Ты реши что искать - наибольшую длину или наименьшую сумму. Это примерно как самый дешевый, но самый сладкий. Что делать если самый дешевый не самый сладкий?

Опять же. в дереве поиска вершины в левом поддереве меньше вершин в правом. Поэтому минимальная сумма на концах будет у двух самых левых листовых вершин, а в пути будет ровно 2 вершины (всегда).

 

[Maestresa]

Не понятно как этот код с задачей связан. Это раз.
Не понятна задача. Это два.
Не понятно как условие задачи связано с "выходные данные". Это три.



Путь максимальной длины - это одно - тебе надо просто найти 2 наиболее глубоких вершины.
Сумма ключей минимальная - это совсем другое. Как так, "максимальной длины, у которого сумма минимальна" - не понятно. Ты реши что искать - наибольшую длину или наименьшую сумму. Это примерно как самый дешевый, но самый сладкий. Что делать если самый дешевый не самый сладкий?

Опять же. в дереве поиска вершины в левом поддереве меньше вершин в правом. Поэтому минимальная сумма на концах будет у двух самых левых листовых вершин, а в пути будет ровно 2 вершины (всегда).

Условия дала в том виде, в котором нам его дал преподаватель. Поясню код: ну построение дерева это понятно, далее я ищу высоту каждой вершины(самый динный путь в дугах до листа), затем ищу максимальную длину пути, проходящего через каждый узел(находится по формуле макс.дл.пути=количество сыновей+высоты сыновей)
Поясню условие задачи: в бинарном поисковом дереве может существовать несколько путей одинаковой длины с одинаковым или разными корнями. Я нашла максимальные пути, проходящие через каждый узел, т.е. автоматически нашла и корни каждого из путей. Итак, из этих максимальных путей остается выбрать тот, у которого сумма конечных вершин минимальна. Ведь для каждого пути будет своя сумма конечных вершин. Как я понимаю мне нужно для каждого такого пути найти сумму конечных вершин и удалять уже ту вершину, которая будет являться корнем пути максимальной длины и к тому же иметь минимальную сумму.