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

@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, ты, наверно, просто неумело троллишь. Тема закрыта с пятого поста.

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

@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

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

Решение