Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ По входной последовательности построить дерево бинарного поиска и найти количество узлов, имеющих только одного левого потомка http://www.cyberforum.ru/cpp-beginners/thread805886.html
Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен Задача 8...
C++ Списки. Удалить каждое последующее вхождение символа если он встречался до этого. Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен Задача 7... http://www.cyberforum.ru/cpp-beginners/thread805884.html
Очередь. Удалить каждое последующее вхождение символа если он встречался до этого. C++
Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен задача 6...
C++ Закомментировать
#include <iostream> using namespace std; int main() { int a,b,a1,b1,r; r=1; cout << "Pervoe chislo = "; cin >> a; cout << "Vtoroe chislo = ";
C++ Удалить каждое последующее вхождение символа если он встречался до этого http://www.cyberforum.ru/cpp-beginners/thread805871.html
Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен Задача...
C++ Создать класс Point для работы с точками на плоскости Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен Задача 3... подробнее

Показать сообщение отдельно
Priorzivil
0 / 0 / 0
Регистрация: 11.03.2013
Сообщений: 11

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

11.03.2013, 18:07. Просмотров 1940. Ответов 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru