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

Тема в разделе "C/C++/C#", создана пользователем Maestresa, 24 фев 2014.

  1. Maestresa

    Maestresa New Member

    Регистрация:
    16 фев 2014
    Сообщения:
    3
    Симпатии:
    0
    Помогите пожалуйста решить задачу.
    Условие
    Найти такой путь максимальной длины между вершинами дерева, у которого сумма ключей конечных вершин минимальна. Удалить (правым удалением) корневую вершину этого пути.

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

    Выходные данные
    out.txt содержит массив вершин, полученный прямым левым обходом итогового дерева.
    Код (C++):
    #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;
    }
    вот нашла высоты всех узлов, нашла максимальные длины путей, проходящих через каждый узел и зашла в тупик: как же теперь разобраться с минимальной суммой конечных вершин?
    в задаче есть ограничение на количество обходов дерева(не больше двух без учета построния)
    может у кого есть идеи что же тут дальше делать?
     
  2. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    Не понятно как этот код с задачей связан. Это раз.
    Не понятна задача. Это два.
    Не понятно как условие задачи связано с "выходные данные". Это три.

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

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

    Maestresa New Member

    Регистрация:
    16 фев 2014
    Сообщения:
    3
    Симпатии:
    0
    Условия дала в том виде, в котором нам его дал преподаватель. Поясню код: ну построение дерева это понятно, далее я ищу высоту каждой вершины(самый динный путь в дугах до листа), затем ищу максимальную длину пути, проходящего через каждый узел(находится по формуле макс.дл.пути=количество сыновей+высоты сыновей)
    Поясню условие задачи: в бинарном поисковом дереве может существовать несколько путей одинаковой длины с одинаковым или разными корнями. Я нашла максимальные пути, проходящие через каждый узел, т.е. автоматически нашла и корни каждого из путей. Итак, из этих максимальных путей остается выбрать тот, у которого сумма конечных вершин минимальна. Ведь для каждого пути будет своя сумма конечных вершин. Как я понимаю мне нужно для каждого такого пути найти сумму конечных вершин и удалять уже ту вершину, которая будет являться корнем пути максимальной длины и к тому же иметь минимальную сумму.
     
Загрузка...
Похожие Темы - Бинарное Поисковое Дерево
  1. newslayer
    Ответов:
    0
    Просмотров:
    1.114
  2. European
    Ответов:
    0
    Просмотров:
    2.069

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