Форум программистов, компьютерный форум CyberForum.ru

Дерево турнира с выбыванием - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
14.11.2012, 19:00     Дерево турнира с выбыванием #1
Не совсем понимаю, как осуществить процедуру заполнения дерева. Точнее, не понимаю, как поместить в корень максимальный элемент.
Имеется вот такое дерево с симметричным обходом. Нужно с помощью турнира с выбыванием отсортировать данный массив. Заранее благодарен за помощь.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#define _CRT_SECURE_NO_WARNINGS
#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <conio.h>
using namespace std;
struct tree 
{
    int info;
    tree *right;
    tree *left;
};
tree *create_tree(tree *current, int element)
{
   if (current==NULL) 
     {
        current = new tree;
        current->info = element;
        current->right = NULL;
        current->left = NULL;
        return current;
     }
   if (current->info < element)          
     current->right = create_tree(current->right, element);
   else
     current->left  = create_tree(current->left, element);
   return current;
}
void simmetric(tree *current,int l)
{
   if(current!=NULL)
    {
        simmetric(current->left,l+1);
        for(int i=0;i<l;i++)
            cout << "\t";
        cout << current->info << endl;
        simmetric(current->right,l+1);        
    }
}
void show_tree(int massive[], int mcounter)       
{
   tree *current;
   current = NULL;
   for (int i=0; i<mcounter; i++)        
      current = create_tree(current, massive[i]);     
   cout<<"\nSymmetric: \n";
   simmetric(current,0); 
}
void delete_tree(tree **current)
{
    int count=13;
    if(*current!=NULL)
    {
        delete_tree(&(*current)->left);
        delete_tree(&(*current)->right);
        delete *current;
        count--;
        if(count==0)
            *current=NULL;
    }
}
void showsymmetric(tree *current,int l)
{
    if(current!=NULL)
    {
        showsymmetric(current->left,l+1);
        for(int i=0;i<l;i++)
            cout << "\t";
        cout << current->info << endl;
        showsymmetric(current->right,l+1);
    }
    delete_tree(&current);
}
int main()
{
int massive [13] = {5, 9, 13, 14, 2, 7, 1, 15, 18, 8, 4, 3, 50};
show_tree(massive,13);
getch();
return 0;
P.S. Можно код не исправлять, а просто объяснить принцип, я постараюсь понять)

Добавлено через 1 час 3 минуты
ап штоле)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
14.11.2012, 19:09     Дерево турнира с выбыванием #2
можешь нарисовать пример, какое дерево ты хочешь получить?
Или наоборот этот рисунок тебе и требуется в ответе?
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
14.11.2012, 23:06  [ТС]     Дерево турнира с выбыванием #3
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
можешь нарисовать пример, какое дерево ты хочешь получить?
Или наоборот этот рисунок тебе и требуется в ответе?
В корне дерева должен лежать наибольший элемент. Соответственно, этот же элемент должен находиться в каждой правой ветви дерева. Я бы нарисовал, да нет возможности)
Ну как в турнирных таблицах: отборочные, четвертьфиналы, полуфиналы и финалы, где побеждает сильнейший. Тут "побеждает" наибольший.
Задача - построить такое дерево, поместив в него данный массив)
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
17.11.2012, 14:48  [ТС]     Дерево турнира с выбыванием #4
Таки ап еще разок
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
17.11.2012, 15:02  [ТС]     Дерево турнира с выбыванием #5
Должно получиться примерно такое дерево
Миниатюры
Дерево турнира с выбыванием  
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11841 / 6820 / 771
Регистрация: 27.09.2012
Сообщений: 16,911
Записей в блоге: 2
Завершенные тесты: 1
17.11.2012, 15:04     Дерево турнира с выбыванием #6
Рекурсия и рекурсивные алгоритмы
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
17.11.2012, 22:18     Дерево турнира с выбыванием #7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <list>
#include <ctime> 
using namespace std;
struct node{
    int value;
    int level;
    node* left;
    node* right;
    node(int val=0):value(val), right(NULL), left(NULL), level(0){};
};
list<node*> fill(){
    list<node*> buffer;
    int n;
    struct node* new_elem;
    srand(time(NULL));
    cout<<"input n of elems:";
    cin>>n;
    cout<<"elements are:";
    while(n--)
    {
        new_elem=new node(rand()%90+10);
        cout<<(new_elem->value)<<", ";
        buffer.push_back(new_elem);
    }
    cout<<endl;
    return buffer;
}
node* build_tree(list<node*> buffer){
    node* a;
    node* b;
    node* parent_of_a_b;
 
    while (!buffer.empty()){
        a=buffer.front();
        buffer.pop_front();
        if (buffer.empty())
            return a;
        b=buffer.front();
        buffer.pop_front();
        parent_of_a_b=new node(max(a->value, b->value));
        parent_of_a_b->left=a;
        parent_of_a_b->right=b;
        parent_of_a_b->level=max(a->level, b->level)+1;
        buffer.push_back(parent_of_a_b);    
    }
 
}
void print_level(int lvl, node* root){
    if (root->level>lvl){
        print_level(lvl, root->left);
        print_level(lvl, root->right);
    }
    else{
        if (root->level==lvl){
            cout<<root->value;
            for (int i=0; i<4*(1<<lvl)-2; i++)
                cout<<" ";
        }
    }
 
}
void print_tree(node* root){
    cout<<"THE TREE:"<<endl;
    for (int i=(root->level); i>=0; i--){
        for (int j=0; j<2*(1<<i)-2; j++)
            cout<<" ";
        print_level(i, root);
        cout<<endl;
    }
}
int main() // Оcновное тело программы
{
    list<node*> buffer;
    node* root;
    buffer=fill();
    root=build_tree(buffer);
    print_tree(root);
    system("PAUSE");
}
Правда рисуется кривовато, но ты там посмотри, сколько пробелов между числами в цикле ставить...
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
17.11.2012, 22:31  [ТС]     Дерево турнира с выбыванием #8
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <list>
#include <ctime> 
using namespace std;
struct node{
    int value;
    int level;
    node* left;
    node* right;
    node(int val=0):value(val), right(NULL), left(NULL), level(0){};
};
list<node*> fill(){
    list<node*> buffer;
    int n;
    struct node* new_elem;
    srand(time(NULL));
    cout<<"input n of elems:";
    cin>>n;
    cout<<"elements are:";
    while(n--)
    {
        new_elem=new node(rand()%90+10);
        cout<<(new_elem->value)<<", ";
        buffer.push_back(new_elem);
    }
    cout<<endl;
    return buffer;
}
node* build_tree(list<node*> buffer){
    node* a;
    node* b;
    node* parent_of_a_b;
 
    while (!buffer.empty()){
        a=buffer.front();
        buffer.pop_front();
        if (buffer.empty())
            return a;
        b=buffer.front();
        buffer.pop_front();
        parent_of_a_b=new node(max(a->value, b->value));
        parent_of_a_b->left=a;
        parent_of_a_b->right=b;
        parent_of_a_b->level=max(a->level, b->level)+1;
        buffer.push_back(parent_of_a_b);    
    }
 
}
void print_level(int lvl, node* root){
    if (root->level>lvl){
        print_level(lvl, root->left);
        print_level(lvl, root->right);
    }
    else{
        if (root->level==lvl){
            cout<<root->value;
            for (int i=0; i<4*(1<<lvl)-2; i++)
                cout<<" ";
        }
    }
 
}
void print_tree(node* root){
    cout<<"THE TREE:"<<endl;
    for (int i=(root->level); i>=0; i--){
        for (int j=0; j<2*(1<<i)-2; j++)
            cout<<" ";
        print_level(i, root);
        cout<<endl;
    }
}
int main() // Оcновное тело программы
{
    list<node*> buffer;
    node* root;
    buffer=fill();
    root=build_tree(buffer);
    print_tree(root);
    system("PAUSE");
}
Правда рисуется кривовато, но ты там посмотри, сколько пробелов между числами в цикле ставить...
Спасибо) Правда нам используя стандартные библиотеки надо реализовать)
Но все равно спасибо, буду ковырять)

Добавлено через 1 минуту
В книге седжвика нашел алгоритм реализации турнирного дерева и переделал под свои цели, но... Что-то там больно большое дерево получается)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
tree *tournament(tree *current, int massive[],int l,int r)
{
    int m = (l+r)/2;
    current = new tree;
    current->info = massive[m];
    current->right = NULL;
    current->left = NULL;
    if (l == r) 
        return current;
    current->left = tournament (current->left,massive, 1, m) ;
    current->right = tournament (current->right,massive, m+1, r) ;
    int u = current->left->info;
    int v = current->right->info;
    if (u > v) 
        current->info = u; 
    else current->info=v;
    return current;
}
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
17.11.2012, 22:35     Дерево турнира с выбыванием #9
так единственный шаблон у меня это <list>
в список я пихаю узлы перед тем как построить дерево. Это чисто вспомогательная штуковина.
Само дерево состоит из простых узлов
C++
1
2
3
4
5
6
struct node{
    int value;
    int level;
    node* left;
    node* right;
};
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
17.11.2012, 22:41  [ТС]     Дерево турнира с выбыванием #10
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
так единственный шаблон у меня это <list>
в список я пихаю узлы перед тем как построить дерево. Это чисто вспомогательная штуковина.
Само дерево состоит из простых узлов
C++
1
2
3
4
5
6
struct node{
    int value;
    int level;
    node* left;
    node* right;
};
Дак у меня в том и проблема, что я не знаю, как сделать так, чтобы в корень поместить наибольший элемент. Понятно, что через рекурсию как-то надо от листьев к корню идти, но как это сделать - я не знаю, уже замучался думать)
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
17.11.2012, 23:00     Дерево турнира с выбыванием #11
Я сам с stl не очень дружу, но тут всё просто:
все узлы кладём в очередь. Очередь в STL это <list>
Список точнее очередь это структура данных, где мы берём с одного конца элементы, а записываем в другой.

достаём первую пару из начала очереди
создаём для них new родителя
родитель->left=первый элемент очереди
родитель->right=второй элемент очереди.
далее удаляем эти два элемента из очереди
а родителя пихаем в конец очереди, чтобы рано или поздно дойти до него и в свою очередь создать ему родителя.

но пока до конца очереди ещё далеко, мы продолжаем брать первые пары элементов и удалять после создания им родителя.
и так пока не останется только один элемент в очереди.
его мы возвращаем в качестве корня дерева.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.11.2012, 15:01     Дерево турнира с выбыванием
Еще ссылки по теме:

C++ Сортировка числовых массивов методом турнира с выбыванием
C++ Дерево дерево, странное дерево
C++ Таблица хоккейного турнира

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
18.11.2012, 15:01  [ТС]     Дерево турнира с выбыванием #12
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Я сам с stl не очень дружу, но тут всё просто:
все узлы кладём в очередь. Очередь в STL это <list>
Список точнее очередь это структура данных, где мы берём с одного конца элементы, а записываем в другой.

достаём первую пару из начала очереди
создаём для них new родителя
родитель->left=первый элемент очереди
родитель->right=второй элемент очереди.
далее удаляем эти два элемента из очереди
а родителя пихаем в конец очереди, чтобы рано или поздно дойти до него и в свою очередь создать ему родителя.

но пока до конца очереди ещё далеко, мы продолжаем брать первые пары элементов и удалять после создания им родителя.
и так пока не останется только один элемент в очереди.
его мы возвращаем в качестве корня дерева.
А без очереди никак? Головой-то вроде понял, но программно это представить для меня сложновато...
И опять же, мне нужно не используя <stl> реализовать дерево.
Yandex
Объявления
18.11.2012, 15:01     Дерево турнира с выбыванием
Ответ Создать тему
Опции темы

Текущее время: 02:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru