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

Тема в разделе "Общие вопросы по С и С++", создана пользователем Guest_, 7 апр 2006.

Статус темы:
Закрыта.
  1. Guest_

    Guest_ Гость

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

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

    ___________________________________________________________________

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

    Код (Text):
    #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
     
Загрузка...
Похожие Темы - Интересная задача
  1. beloff
    Ответов:
    11
    Просмотров:
    2.409
  2. beloff
    Ответов:
    13
    Просмотров:
    2.741
  3. vbs
    Ответов:
    9
    Просмотров:
    4.028
  4. Янчик
    Ответов:
    0
    Просмотров:
    481
  5. TrishaRay
    Ответов:
    1
    Просмотров:
    781
Статус темы:
Закрыта.

Поделиться этой страницей