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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Priorzivil
0 / 0 / 0
Регистрация: 11.03.2013
Сообщений: 11
11.03.2013, 18:07     По входной последовательности построить идеально сбалансированное дерево #1
Народ меня тут 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++

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

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

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