CyberForum.ru - Форум программистов и сисадминов
Вернуться   Форум программистов и сисадминов CyberForum.ru > Форум программистов > Форум C++
Перезагрузить страницу

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

Регистрация Правила Блоги Пользователи Социальные группы Поиск Сообщения за день Все разделы прочитаны

Ответ Создать новую тему
Страница 1 из 2 1 2 »
 
Старый 23.12.2011, 19:08   #1
iama
Серая масса
Эксперт C++
 
Аватар для iama
 
Регистрация: 30.07.2010
Адрес: 0xDEADBEEF
Сообщений: 3,444
Репутация: 1008 (757)
По умолчанию Высота бинарного дерева поиска
Что неправильно в программе?
Полное условие

Код 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

#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;
}
 
iama вне форума
Другие темы раздела
C++ Как получить TID текущего потока? (библиотека pthread, компилятор g++ 4.6.1 открытый вопрос niXmanу)
Да, как? #include <windows.h> #include <pthread.h> #include <stdio.h> #include <stdlib.h> void *BusyWork(void *t) { printf("TID= %x\n", pthread_self()); printf("TID= %x\n", (unsigned int)GetCurrentThreadId ()); return NULL;. Как получить TID текущего потока? (библиотека pthread, компилятор g++ 4.6.1 открытый вопрос niXmanу) 		Совместимость кода Code Composer Studio (CCS) с C/C++
С преподавателем друг друга не поняли. Как результат, прихожу с честно сделанными в Паскале лабами под занавес года, а он мне встречный подарок: "раз ты так редко ходишь, то почему не сделал лабы в CCS?". В общем логика железная. Пошел гуглить что это за CCS. А вся группа вовсе не делала этих лаб,.... Совместимость кода Code Composer Studio (CCS) с C/C++
Старый 23.12.2011, 20:18   #2
go
Форумчанин
 
Регистрация: 16.04.2009
Сообщений: 3,209
Репутация: 2116 (993)
По умолчанию Re: Высота бинарного дерева поиска
А может схитрить? Хранить еще и высоту каждого "элемента". При добавлении элемента еще и высоту вычислять (родитель + 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;
go вне форума
Старый 23.12.2011, 20:21  [ТС]   #3
iama
Серая масса
Эксперт C++
 
Аватар для iama
 
Регистрация: 30.07.2010
Адрес: 0xDEADBEEF
Сообщений: 3,444
Репутация: 1008 (757)
По умолчанию Re: Высота бинарного дерева поиска
Там была примитивная бага, я изменял 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
130

#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;
}
 
iama вне форума
Старый 23.12.2011, 20:33   #4
go
Форумчанин
 
Регистрация: 16.04.2009
Сообщений: 3,209
Репутация: 2116 (993)
По умолчанию Re: Высота бинарного дерева поиска
Цитата Сообщение от 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);
    }
}
go вне форума
Старый 23.12.2011, 20:55  [ТС]   #5
iama
Серая масса
Эксперт C++
 
Аватар для iama
 
Регистрация: 30.07.2010
Адрес: 0xDEADBEEF
Сообщений: 3,444
Репутация: 1008 (757)
По умолчанию Re: Высота бинарного дерева поиска
Не так там было то, что для пустого дерева выводился ноль, а не должен был.
iama вне форума
Старый 23.12.2011, 21:12   #6
go
Форумчанин
 
Регистрация: 16.04.2009
Сообщений: 3,209
Репутация: 2116 (993)
По умолчанию Re: Высота бинарного дерева поиска
Ошибки в построении. Ясно, что ноль. Ваш 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;
}
go вне форума
Старый 24.12.2011, 19:24  [ТС]   #7
iama
Серая масса
Эксперт C++
 
Аватар для iama
 
Регистрация: 30.07.2010
Адрес: 0xDEADBEEF
Сообщений: 3,444
Репутация: 1008 (757)
По умолчанию Re: Высота бинарного дерева поиска
go, не выпендривайся. Писалось под конкретную задачу, а не в общем случае. Не учел одного крайнего контрпримера, бывает. Что ж тебя так в моём мейне убило-то?
iama вне форума
Старый 24.12.2011, 19:52   #8
go
Форумчанин
 
Регистрация: 16.04.2009
Сообщений: 3,209
Репутация: 2116 (993)
По умолчанию Re: Высота бинарного дерева поиска
Ну во-первых его размер.
Во-вторых вы посылаете в функцию подсчета листов указатель константу. Ну ясное дело, что он всегда == истина, и соответственно функция будет думать, что дерево не пустое. В пору думать и динамических массивах.

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

Не по теме:
Цитата Сообщение от iama Посмотреть сообщение
go, не выпендривайся.
Это я так понимаю вместо спасибо
Не обижайтесь, просто так мэйн закрутили, что черт ногу сломит.
go вне форума
Старый 24.12.2011, 21:10  [ТС]   #9
iama
Серая масса
Эксперт C++
 
Аватар для iama
 
Регистрация: 30.07.2010
Адрес: 0xDEADBEEF
Сообщений: 3,444
Репутация: 1008 (757)
По умолчанию Re: Высота бинарного дерева поиска
Цитата Сообщение от go Посмотреть сообщение
Ну во-первых его размер.
Для решения вышуеказаной задачи другой размер и не нужен.
В олимпиадном программирование классически используются статические массивы вместо динамических, что дает значительный прирост производительности.
Цитата Сообщение от go Посмотреть сообщение
Во-вторых вы посылаете в функцию подсчета листов указатель константу. Ну ясное дело, что он всегда == истина, и соответственно функция будет думать, что дерево не пустое. В пору думать и динамических массивах.
Вообще не понял, к чему ты это. Программа выдает правильные результаты для всех наборов входных данных - больше ничего и не нужно.
Цитата Сообщение от go Посмотреть сообщение
Это я так понимаю вместо спасибо
Просто я не люблю снисходительный тон в мой адрес от анонимов, когда нет предпосылок уважать говорящего.

Того, что тот код - говнокод, я не отрицаю, но другого в этой ситуации и не нужно (тут вообще лучше бинарной кучей реализовывать)
iama вне форума
После регистрации реклама в сообщениях будет скрыта
Старый 24.12.2011, 21:34   #10
go
Форумчанин
 
Регистрация: 16.04.2009
Сообщений: 3,209
Репутация: 2116 (993)
По умолчанию Re: Высота бинарного дерева поиска

Не по теме:
Цитата Сообщение от iama Посмотреть сообщение
Для решения вышуеказаной задачи другой размер и не нужен.
А при чем здесь размер?

Цитата Сообщение от iama Посмотреть сообщение
классически используются статические массивы вместо динамических,
Был бы динамический, не было проблем
Код C++
1
2
3
4

int *ans = NULL;
 
if (a != 0)
                {    ans = new int [10000];
Добавлено через 2 минуты
Цитата Сообщение от iama Посмотреть сообщение
Того, что тот код - говнокод, я не отрицаю,
Ваш код не читаем. Вы сами сделали ошибку, только из-за своего кода.
Цитата Сообщение от iama Посмотреть сообщение
от анонимов
Я с Вами знаниями не мерелся

Добавлено через 1 минуту
Цитата Сообщение от iama Посмотреть сообщение
Программа выдает правильные результаты для всех наборов входных данных - больше ничего и не нужно.
При малейшем сбое сразу на форму, чтобы другие Ваш "гавнокод" разбирали (здесь нет ни малейшего упрека)?


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

Не по теме:
Вам помогли? Не нравится? Имеете что-либо против меня? Тогда отписываюсь от этой темы
go вне форума
Ответ Создать новую тему
Страница 1 из 2 1 2 »

Похожие темы
Тема Автор
C# .NET визуализация бинарного дерева поиска под WPF
Недавно столкнулся с проблемой визуализации бинарного дерева поиска. Ничего кроме реализации вручную с помощью кнопок и линий в голову не приходит. Может быть кто-то подскажет готовую удобную библиотеку под WPF ?? Заранее огромное спасибо всем откликнувшимся. 		alex010503
С++ для начинающих Итератор для бинарного дерева поиска.
Господа, нужен совет знатоков. Бинарное дерево поиска представлено следующей структурой. template <typename ValueType> struct Node { ValueType value; Node *left; Node *right; } Вопрос заключается в следующем: каким образом реализуется итератор (хотя бы однонаправленный) для такой... 		lemegeton
C++ Builder обход бинарного дерева поиска
Добрый день, не могу понять как с помощью TImage и Canvas вывести собственно дерево поиска, причем в консоли я его вывожу повернутым на 90 градусов т.е. так 40 20 15 10 9 7 6 5 		AllwaysPain
С++ для начинающих Распечатка бинарного дерева поиска
Много где висит функция void print(int deep, ptree p) { if(p) { print(deep + 1, p->l); for ( int i = 0; i < deep; i ++ ) printf(" " ); printf(">%d",p->val); 		xMURNx
С++ для начинающих (ищу) Алгоритм построения бинарного дерева поиска
Помогите пожалуйста. Если у кого завалялся алгоритм построения бинарного дерева поиска. Поделитесь. Очень нужно. Желательно что-бы цифры ставились рендомом. Но, как получится. Благодарю. 		Avariya
Опции темы

Текущее время: 01:04. Часовой пояс GMT +4.

Компьютерный форум программистов и сисадминов
Реклама - Обратная связь - Вверх
Powered by vBulletin® Version 3.8.7 PL2
Copyright ©2000 - 2012, vBulletin Solutions, Inc. 		Рейтинг@Mail.ru Яндекс.Метрика