Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.91/47: Рейтинг темы: голосов - 47, средняя оценка - 4.91
1334 / 985 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
1

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

23.12.2011, 20:08. Просмотров 9806. Ответов 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.12.2011, 20:08
Ответы с готовыми решениями:

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

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

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

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

10
go
Эксперт С++
3639 / 1371 / 243
Регистрация: 16.04.2009
Сообщений: 4,527
23.12.2011, 21:18 2
Лучший ответ Сообщение было отмечено как решение

Решение

А может схитрить? Хранить еще и высоту каждого "элемента". При добавлении элемента еще и высоту вычислять (родитель + 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
1334 / 985 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
23.12.2011, 21:21  [ТС] 3
Там была примитивная бага, я изменял 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
Эксперт С++
3639 / 1371 / 243
Регистрация: 16.04.2009
Сообщений: 4,527
23.12.2011, 21:33 4
Цитата Сообщение от 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
1334 / 985 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
23.12.2011, 21:55  [ТС] 5
Не так там было то, что для пустого дерева выводился ноль, а не должен был.
0
go
Эксперт С++
3639 / 1371 / 243
Регистрация: 16.04.2009
Сообщений: 4,527
23.12.2011, 22:12 6
Ошибки в построении. Ясно, что ноль. Ваш 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
1334 / 985 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
24.12.2011, 20:24  [ТС] 7
go, не выпендривайся. Писалось под конкретную задачу, а не в общем случае. Не учел одного крайнего контрпримера, бывает. Что ж тебя так в моём мейне убило-то?
0
go
Эксперт С++
3639 / 1371 / 243
Регистрация: 16.04.2009
Сообщений: 4,527
24.12.2011, 20:52 8
Ну во-первых его размер.
Во-вторых вы посылаете в функцию подсчета листов указатель константу. Ну ясное дело, что он всегда == истина, и соответственно функция будет думать, что дерево не пустое. В пору думать и динамических массивах.

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

Не по теме:

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

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

Того, что тот код - говнокод, я не отрицаю, но другого в этой ситуации и не нужно (тут вообще лучше бинарной кучей реализовывать)
0
go
Эксперт С++
3639 / 1371 / 243
Регистрация: 16.04.2009
Сообщений: 4,527
24.12.2011, 22:34 10

Не по теме:

Цитата Сообщение от 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
1334 / 985 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
25.12.2011, 00:50  [ТС] 11
go, ты, наверно, просто неумело троллишь. Тема закрыта с пятого поста.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.12.2011, 00:50

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.