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

Вот условие:
Найти вершины, через которые проходит наибольшее количество путей максимальной длины, и удалить их (правым удалением).
Входные данные
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