Форум программистов, компьютерный форум, киберфорум
C++
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.85/75: Рейтинг темы: голосов - 75, средняя оценка - 4.85
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297

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

23.12.2011, 20:08. Показов 15518. Ответов 10
Метки нет (Все метки)
Студворк — интернет-сервис помощи студентам
Что неправильно в программе?
Полное условие

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;
}
0
Лучшие ответы (1)
Сообщение: #2321703
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
 23.12.2011, 20:08
Ответы с готовыми решениями:

Организация бинарного дерева поиска
Всем доброго времени суток. Передо мной встала задача организовать чтение файла и подсчёт повторений слов с помощью бинарного дерева...

Обход бинарного дерева
люди, выручайте, очень срочно нужен исходник для обхода бинарного дерева, хоть на С++, хоть на Паскале. У кого есть киньте, нужно...

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

10
go
Эксперт С++
3646 / 1378 / 243
Регистрация: 16.04.2009
Сообщений: 4,526
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;
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
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;
}
0
go
Эксперт С++
3646 / 1378 / 243
Регистрация: 16.04.2009
Сообщений: 4,526
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);
    }
}
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
23.12.2011, 21:55  [ТС]
Не так там было то, что для пустого дерева выводился ноль, а не должен был.
0
go
Эксперт С++
3646 / 1378 / 243
Регистрация: 16.04.2009
Сообщений: 4,526
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;
}
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
24.12.2011, 20:24  [ТС]
go, не выпендривайся. Писалось под конкретную задачу, а не в общем случае. Не учел одного крайнего контрпримера, бывает. Что ж тебя так в моём мейне убило-то?
0
go
Эксперт С++
3646 / 1378 / 243
Регистрация: 16.04.2009
Сообщений: 4,526
24.12.2011, 20:52
Ну во-первых его размер.
Во-вторых вы посылаете в функцию подсчета листов указатель константу. Ну ясное дело, что он всегда == истина, и соответственно функция будет думать, что дерево не пустое. В пору думать и динамических массивах.

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

Не по теме:

Цитата Сообщение от iama Посмотреть сообщение
go, не выпендривайся.
Это я так понимаю вместо спасибо ;)
Не обижайтесь, просто так мэйн закрутили, что черт ногу сломит.

0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
24.12.2011, 22:10  [ТС]
Цитата Сообщение от go Посмотреть сообщение
Ну во-первых его размер.
Для решения вышуеказаной задачи другой размер и не нужен.
В олимпиадном программирование классически используются статические массивы вместо динамических, что дает значительный прирост производительности.
Цитата Сообщение от go Посмотреть сообщение
Во-вторых вы посылаете в функцию подсчета листов указатель константу. Ну ясное дело, что он всегда == истина, и соответственно функция будет думать, что дерево не пустое. В пору думать и динамических массивах.
Вообще не понял, к чему ты это. Программа выдает правильные результаты для всех наборов входных данных - больше ничего и не нужно.
Цитата Сообщение от go Посмотреть сообщение
Это я так понимаю вместо спасибо
Просто я не люблю снисходительный тон в мой адрес от анонимов, когда нет предпосылок уважать говорящего.

Того, что тот код - говнокод, я не отрицаю, но другого в этой ситуации и не нужно (тут вообще лучше бинарной кучей реализовывать)
0
go
Эксперт С++
3646 / 1378 / 243
Регистрация: 16.04.2009
Сообщений: 4,526
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

0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
25.12.2011, 00:50  [ТС]
go, ты, наверно, просто неумело троллишь. Тема закрыта с пятого поста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
 25.12.2011, 00:50
Помогаю со студенческими работами здесь

Поиск заданного элемента бинарного дерева
Добрый вечер! Нужна ваша помощь в написании процедуры поиска заданного пользователем элемента дерева. struct Node { float data; ...

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

Функция: подсчет количества вершин на N-ом уровне бинарного дерева
Помогите пожалуйста написать функцию ,которая подсчитывает число вершин на N-ом уровне бинарного дерева T(корень считать вершиной 0-го...

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

Высота бинарного дерева
Надо найти высоту бинарного дерева.


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Новые блоги и статьи
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
 Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Условия использования - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru