Высота бинарного дерева поиска

@iama · Регистрация: 30.07.2010

Студворк — интернет-сервис помощи студентам

Что неправильно в программе?
Полное условие

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
105
#include <iostream>
 
#include <cstdio>
 
#pragma comment (linker, "/stack:250000000")
 
using namespace std;
 
struct node
{
    node *left, *right;
    int val;
};
 
int q;
node tr[100000];
 
int tree_insert (node *root, int val)
{
    node *fr = root;
    int h = 1;
 
    while (fr)
    {
        if (fr->val == val)
            return h;
 
        if (fr->val > val)
        {
            root = fr;
            fr = fr->left;
 
            if (fr == NULL)
            {
                fr = &tr[++q];
                root->left = fr;
 
                fr->left = NULL;
                fr->right = NULL;
 
                fr->val = val;
 
                break;
            }
        }
 
        if (fr->val < val)
        {
            root = fr;
            fr = fr->right;
 
            if (fr == NULL)
            {
                fr = &tr[++q];
                root->right = fr;
 
                fr->left = NULL;
                fr->right = NULL;
 
                fr->val = val;
 
                break;
            }
        }
 
        h++;
    }
 
    return ++h;
}
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    int l, a;
 
    l = 0;
    cin >> a;
 
    if (a != 0)
    {
        l = 1;
        q = 0;
        tr[0].val = a;
 
        tr[0].left = NULL;
        tr[0].right = NULL;
    }
 
    while (a != 0)
    {
        cin >> a;
 
        if (a == 0)
            break;
 
        l = max(l, tree_insert(tr, a));
    }
 
    cout << l << endl;
 
    return 0;
}

go · 23.12.2011, 21:18

А может схитрить? Хранить еще и высоту каждого "элемента". При добавлении элемента еще и высоту вычислять (родитель + 1). Потом любым обходом вычислить макс из высот?

Добавлено через 8 минут
Если нет, то вот делал когда-то на паскале

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
function height(p: adrzv): integer;
var l, r: integer;
begin
if p <> nil then
  begin
  l := height(p^.left);
  r := height(p^.right);
  if l > r then height := l + 1
  else height := r + 1
  end
else
  height := 0;
end;

@iama · 23.12.2011, 21:21 **[ТС]**

Там была примитивная бага, я изменял fr, а потом еще раз смотрел (fr->val < val).

Такой еще вопрос, нужно вывести все листья б-дерева, что я неправильно?

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <algorithm>
 
#include <cstdio>
 
#pragma comment (linker, "/stack:250000000")
 
using namespace std;
 
struct node
{
    node *left, *right;
    int val;
};
 
int q, aq, ans[100000];
node tr[100000];
 
int tree_insert (node *root, int val)
{
    node *fr = root;
    int h = 1;
 
    while (fr)
    {
        if (fr->val == val)
            return h;
        else
        if (fr->val > val)
        {
            root = fr;
            fr = fr->left;
 
            if (fr == NULL)
            {
                fr = &tr[++q];
                root->left = fr;
 
                fr->left = NULL;
                fr->right = NULL;
 
                fr->val = val;
 
                break;
            }
        }
        else
        if (fr->val < val)
        {
            root = fr;
            fr = fr->right;
 
            if (fr == NULL)
            {
                fr = &tr[++q];
                root->right = fr;
 
                fr->left = NULL;
                fr->right = NULL;
 
                fr->val = val;
 
                break;
            }
        }
 
        h++;
    }
 
    return ++h;
}
 
void dfs (node *n)
{
    if (n->left != NULL)
        dfs(n->left);
 
    if (n->left == NULL && n->right == NULL)
        ans[aq++] = n->val;
 
    if (n->right != NULL)
        dfs(n->right);
}
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    int l, a, i;
    node *n, *p;
 
    l = 0;
    cin >> a;
 
    if (a != 0)
    {
        l = 1;
        q = 0;
        tr[0].val = a;
 
        tr[0].left = NULL;
        tr[0].right = NULL;
    }
 
    while (a != 0)
    {
        cin >> a;
 
        if (a == 0)
            break;
 
        tree_insert(tr, a);
    }
 
    aq = 0;
 
    dfs(tr);
 
    if (aq)
        cout << ans[0];
 
    for (i = 1; i < aq; i++)
        cout << ' ' << ans[i];
 
    cout << endl;
 
    return 0;
}

go · 23.12.2011, 21:33

Сообщение от iama

Такой еще вопрос, нужно вывести все листья б-дерева, что я неправильно?

А что не так?

C++
1
2
3
4
5
6
7
8
9
void list (node * root)
{
    if (root) {
        if ( !root->left && !root->right )
            cout << root->key;
        list (root->left);
        list (root->right);
    }
}

@iama · 23.12.2011, 21:55 **[ТС]**

Не так там было то, что для пустого дерева выводился ноль, а не должен был.

go · 23.12.2011, 22:12

Ошибки в построении. Ясно, что ноль. Ваш main меня убил.
Пробуйте.

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <algorithm>
 
#include <cstdio>
 
#pragma comment (linker, "/stack:250000000")
 
using namespace std;
 
struct node
{
        node *left, *right;
        int val;
};
 
int q, aq, ans[100000];
node tr[100000];
bool fl = false;
 
int tree_insert (node *root, int val)
{
 
        node *fr = root;
        int h = 1;
 
        while (fr)
        {
                if (fr->val == val)
                        return h;
                else
                if (fr->val > val)
                {
                        root = fr;
                        fr = fr->left;
 
                        if (fr == NULL)
                        {
                                fr = &tr[++q];
                                root->left = fr;
 
                                fr->left = NULL;
                                fr->right = NULL;
 
                                fr->val = val;
 
                                break;
                        }
                }
                else
                if (fr->val < val)
                {
                        root = fr;
                        fr = fr->right;
 
                        if (fr == NULL)
                        {
                                fr = &tr[++q];
                                root->right = fr;
 
                                fr->left = NULL;
                                fr->right = NULL;
 
                                fr->val = val;
 
                                break;
                        }
                }
 
                h++;
        }
 
        return ++h;
}
 
void list (node * root)
{
        if (root && fl) {
                if ( !root->left && !root->right )
                        cout << root->val;
                list (root->left);
                list (root->right);
        }
}
 
int main()
{
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
 
 
        int l, a, i;
        node *n, *p;
 
        l = 0;
        cin >> a;
 
        if (a != 0)
        {      
                fl = true;
                l = 1;
                q = 0;
                tr[0].val = a;
 
                tr[0].left = NULL;
                tr[0].right = NULL;
        }
 
        while (a != 0)
        {
                cin >> a;
 
                if (a == 0)
                        break;
 
                tree_insert(tr, a);
        }
 
        aq = 0;
 
        list(tr);
 
        if (aq)
                cout << ans[0];
 
        for (i = 1; i < aq; i++)
                cout << ' ' << ans[i];
 
        cout << endl;
 
        return 0;
}

@iama · 24.12.2011, 20:24 **[ТС]**

go, не выпендривайся. Писалось под конкретную задачу, а не в общем случае. Не учел одного крайнего контрпримера, бывает. Что ж тебя так в моём мейне убило-то?

go · 24.12.2011, 20:52

Ну во-первых его размер.
Во-вторых вы посылаете в функцию подсчета листов указатель константу. Ну ясное дело, что он всегда == истина, и соответственно функция будет думать, что дерево не пустое. В пору думать и динамических массивах.

Добавлено через 2 минуты

Не по теме:

Сообщение от iama

go, не выпендривайся.

Это я так понимаю вместо спасибо ;)
Не обижайтесь, просто так мэйн закрутили, что черт ногу сломит.

@iama · 24.12.2011, 22:10 **[ТС]**

Сообщение от go

Ну во-первых его размер.

Для решения вышуеказаной задачи другой размер и не нужен.
В олимпиадном программирование классически используются статические массивы вместо динамических, что дает значительный прирост производительности.

Сообщение от go

Во-вторых вы посылаете в функцию подсчета листов указатель константу. Ну ясное дело, что он всегда == истина, и соответственно функция будет думать, что дерево не пустое. В пору думать и динамических массивах.

Вообще не понял, к чему ты это. Программа выдает правильные результаты для всех наборов входных данных - больше ничего и не нужно.

Сообщение от go

Это я так понимаю вместо спасибо

Просто я не люблю снисходительный тон в мой адрес от анонимов, когда нет предпосылок уважать говорящего.

Того, что тот код - говнокод, я не отрицаю, но другого в этой ситуации и не нужно (тут вообще лучше бинарной кучей реализовывать)

go · 24.12.2011, 22:34

Не по теме:

Сообщение от iama

Для решения вышуеказаной задачи другой размер и не нужен.

А при чем здесь размер?

Сообщение от iama

классически используются статические массивы вместо динамических,

Был бы динамический, не было проблем

C++
1
2
3
4
int *ans = NULL;
 
if (a != 0)
                {    ans = new int [10000];

Добавлено через 2 минуты

Сообщение от iama

Того, что тот код - говнокод, я не отрицаю,

Ваш код не читаем. Вы сами сделали ошибку, только из-за своего кода.

Сообщение от iama

от анонимов

Я с Вами знаниями не мерелся ;)

Добавлено через 1 минуту

Сообщение от iama

Программа выдает правильные результаты для всех наборов входных данных - больше ничего и не нужно.

При малейшем сбое сразу на форму, чтобы другие Ваш "гавнокод" разбирали (здесь нет ни малейшего упрека)?

Добавлено через 12 минут

Не по теме:

Вам помогли? Не нравится? Имеете что-либо против меня? Тогда отписываюсь от этой темы :D

@iama · 25.12.2011, 00:50 **[ТС]**

go, ты, наверно, просто неумело троллишь. Тема закрыта с пятого поста.

Новые блоги и статьи Все статьи Все блоги /
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	23.12.2011, 21:55 [ТС]
	Не так там было то, что для пустого дерева выводился ноль, а не должен был. 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	24.12.2011, 20:24 [ТС]
	go, не выпендривайся. Писалось под конкретную задачу, а не в общем случае. Не учел одного крайнего контрпримера, бывает. Что ж тебя так в моём мейне убило-то? 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	25.12.2011, 00:50 [ТС]
	go, ты, наверно, просто неумело троллишь. Тема закрыта с пятого поста. 0

Высота бинарного дерева поиска

Решение