Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.89
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
#1

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

23.12.2011, 20:08. Просмотров 5170. Ответов 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;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.12.2011, 20:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Высота бинарного дерева поиска (C++):

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

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

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

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

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

Высота страницы в CppWebBrowser - C++ Builder
Доброе время суток. Подскажите пожалуйста можно ли в CppWebBrowser определить высоту страницы(например в вебе это можно сделать на js)? Ну...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
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;
iama
1250 / 975 / 49
Регистрация: 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;
}
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
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);
    }
}
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
23.12.2011, 21:55  [ТС] #5
Не так там было то, что для пустого дерева выводился ноль, а не должен был.
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
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;
}
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
24.12.2011, 20:24  [ТС] #7
go, не выпендривайся. Писалось под конкретную задачу, а не в общем случае. Не учел одного крайнего контрпримера, бывает. Что ж тебя так в моём мейне убило-то?
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
24.12.2011, 20:52 #8
Ну во-первых его размер.
Во-вторых вы посылаете в функцию подсчета листов указатель константу. Ну ясное дело, что он всегда == истина, и соответственно функция будет думать, что дерево не пустое. В пору думать и динамических массивах.

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

Не по теме:

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

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

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

Не по теме:

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

iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
25.12.2011, 00:50  [ТС] #11
go, ты, наверно, просто неумело троллишь. Тема закрыта с пятого поста.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.12.2011, 00:50
Привет! Вот еще темы с ответами:

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

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

Высота окна - C++ WinAPI
Подскажите, как сделать так, чтобы в Win32 API в Visual сделать высоту окна 0, но при этом нужно запомнить старое значение высоты. есть...

Высота строки в Listview - C++ WinAPI
Как можно задать высоту строки у Listview? Как ширину менять ясно, а про высоту нигде не написано :cry: Буду благодарен за любую наводку...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
25.12.2011, 00:50
Ответ Создать тему
Опции темы

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