1. Набираем команду codeby webinar. Набираем команду для организации и проведения вебинаров. Подробнее ...

    Скрыть объявление
  2. Требуются разработчики и тестеры для проекта codebyOS. Требования для участия в проекте: Знание принципов работы ОС на базе Linux; Знание Bash; Крайне желательное знание CPP, Python, Lua; Навыки системного администрирования. Подробнее ...

    Скрыть объявление
  3. Получи 30.000 рублей. Для получения денег необходимо принять участие в конкурсе авторов codeby. С условиями и призами можно ознакомиться на этой странице ...

    Внимание! Регистрация авторов на конкурс закрыта.

    Скрыть объявление

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

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

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

    Guest_ Гость

    Репутация:
    0
    Задали интересную задачку.

    Вот условие:
    Найти вершины, через которые проходит наибольшее количество путей максимальной длины, и удалить их (правым удалением).
    Входные данные
    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
     
Загрузка...
Похожие Темы - Интересная задача
  1. beloff
    Ответов:
    11
    Просмотров:
    2.502
  2. beloff
    Ответов:
    13
    Просмотров:
    2.918
  3. WebWare Team
    Ответов:
    16
    Просмотров:
    425
  4. vbs
    Ответов:
    9
    Просмотров:
    4.177
  5. petiablack
    Ответов:
    0
    Просмотров:
    69
Статус темы:
Закрыта.

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