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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Priorzivil
0 / 0 / 0
Регистрация: 11.03.2013
Сообщений: 11
#1

По входной последовательности построить идеально сбалансированное дерево - C++

11.03.2013, 18:07. Просмотров 1627. Ответов 0
Метки нет (Все метки)

Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен

Задача 9 Деревья 2
в файле input.txt хранится последовательность целых чисел. По входной последовательности построить идеально сбалансированное дерево и поменять в нем местами узлы, хранящие минимальное и максимальное значение

input:
Код
7 15 10 9 13 12 8 18
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//сначала кол-во чисел, потом сами числа
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
 
using namespace std;
 
class tree {
private:
 
    struct el {
        int val;
        el *l_tree;
        el *r_tree;
 
        el() {
            l_tree = 0;
            r_tree = 0;
        }
    };
 
    el *root;
 
public:
 
    tree() {root = 0;}
 
 
    void push (int n, el *&b) {
        int x;
        if (n > 0) {
            b = new el;
            cin >> x;
            b->val = x;
            b->l_tree = b->r_tree = 0;
            int nl = n / 2;
            int nr = n - nl - 1;
            push(nl, b->l_tree);
            push(nr, b->r_tree);
        }
    }
 
    void add (int n) {
        push(n, root);
    }
 
    //метод выводящий дерево в симметрическом порядке
    void print (el *r = 0) {
        if (r == 0)
            r = root;
 
        if (r->l_tree != 0)
            print (r->l_tree);
 
        cout << r->val << ' ';
 
        if (r->r_tree != 0)
            print (r->r_tree);
    }
 
    //метод ищущий ответ на задачу
    void ans (el*& maxi, el*& mini, el *r) {
        if (r->val > maxi->val)
            maxi = r;
 
        if (r->val < mini->val)
            mini = r;
 
        if (r->l_tree != 0)
            ans (maxi, mini, r->l_tree);
 
        if (r->r_tree != 0)
            ans (maxi, mini, r->r_tree);
    }
 
    void change () {
        el* ma = root;
        el* mi = root;
        ans(ma, mi, root);
        swap (ma->val, mi->val);
    }
 
};
 
int main () {
    freopen("input.txt", "r", stdin);
    
    int x;
 
    tree derevo;
    //для дерева построения дерева бинарного поиска по последовательности нужно вводить только последовательность
    // а для идеальносбалансированного перед последовательностью её длину
    int n;
    cin >> n;
    derevo.add(n);
 
    cout << "Balanced tree:" << endl;
    derevo.print();
    derevo.change();
    cout << endl << "Balanced tree after:" << endl;
    derevo.print();
    return 0;
}
output:
Код
Balanced tree:
9 10 13 15 8 12 18
Balanced tree after:
9 10 13 15 18 12 8
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2013, 18:07     По входной последовательности построить идеально сбалансированное дерево
Посмотрите здесь:

C++ Сбалансированное дерево (бинарное)
C++ Сбалансированное двоичное дерево поиска
C++ Сбалансированное дерево
C++ Сформировать идеально сбалансированное бинарное дерево
Идеально сбалансированное дерево C++
C++ Сбалансированное дерево
Идеально сбалансированное дерево C++
C++ Построить односвязный список из входной последовательности чисел
C++ Идеально сбансированное дерево
Идеально сбалансированное дерево C++
C++ Сбалансированное не бинарное дерево
Построить линейный список из входной последовательности чисел и перестроить его C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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