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

Бинарные деревья - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Alexlx
0 / 0 / 0
Регистрация: 28.11.2010
Сообщений: 25
24.04.2011, 11:59     Бинарные деревья #1
Подсчитать количество элементов на n-уровне бинарного дерева.
Подскажите как можно решить используя любой обход в глубину но без рекурсии я уже 4 дня себе голову ломаю...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2011, 11:59     Бинарные деревья
Посмотрите здесь:

Бинарные деревья C++
Бинарные деревья C++
C++ Бинарные деревья
C++ бинарные деревья
бинарные деревья C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Alexlx
0 / 0 / 0
Регистрация: 28.11.2010
Сообщений: 25
24.04.2011, 12:31  [ТС]     Бинарные деревья #2
Я могу выложить как рекурсивно решить но как без рекурсии я не знаю
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
24.04.2011, 15:57     Бинарные деревья #3
Цитата Сообщение от Alexlx Посмотреть сообщение
Подскажите как можно решить используя любой обход в глубину но без рекурсии
С использованием стека, либо делать дерево как двусвязный список, то есть чтобы потомки содержали указатель на предка.
Alexlx
0 / 0 / 0
Регистрация: 28.11.2010
Сообщений: 25
24.04.2011, 16:13  [ТС]     Бинарные деревья #4
ну я знаю какие обходы бывают и как ими пользоваться))) мне сама идея нужна как можно определять уровень и как подсчитывать на нем элементы..
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
24.04.2011, 16:20     Бинарные деревья #5
Цитата Сообщение от Alexlx Посмотреть сообщение
мне сама идея нужна как можно определять уровень
Идея то проще некуда. Ставите счетчик уровней и увеличиваете его значения с каждым углублением, соответственно уменьшаете с каждым поднятием. Доходите до нужного уровня - увеличиваете счетчик элементов, поднимаетесь до разветвления и опять углубляетесь до нужнгго уровня. Если умеете делать обход дерева, то задача не сложная.
Alexlx
0 / 0 / 0
Регистрация: 28.11.2010
Сообщений: 25
24.04.2011, 16:23  [ТС]     Бинарные деревья #6
щас попробую спасибо за подсказку)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.04.2011, 17:10     Бинарные деревья
Еще ссылки по теме:

Бинарные деревья C++
C++ Бинарные деревья
Бинарные деревья C++

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

Или воспользуйтесь поиском по форуму:
Alexlx
0 / 0 / 0
Регистрация: 28.11.2010
Сообщений: 25
25.04.2011, 17:10  [ТС]     Бинарные деревья #7
ну вот все работает) если кому надо
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
# include "iostream"
# include "stdio.h"
# include "locale.h"
# include "conio.h"
 
using namespace std;
 
struct tree
{   char elem;
    tree *left,*right;};
 
struct stack
{   tree *elem ;
    stack *next;};
 
void in(stack **s, tree *d)
{   stack *q;
    if( *s!=NULL )
    {   q = new stack;
        q->next= (*s);
        q->elem = d;
        *s=q;
    }
    else
    {   (*s) = new stack;
        (*s)->elem = d;
        (*s)->next = NULL;
    }
}
 
void out(stack **s, tree **d)
{   stack *q;
    q = (*s);
    (*s)=q->next;
    (*d) = q->elem;
    delete q;
}
 
tree *build(FILE *file)
{   tree *d;
    char c;
    fscanf(file,"%c",&c);
    if (c == ',') fscanf(file,"%c",&c);
    if (c == '(')
    {
        d = new tree;
        fscanf(file,"%c",&c);
        d->elem = c;
        d->left = build(file);
        d->right = build(file); 
        fscanf(file,"%c",&c);
        return d;
    }
    else return NULL;
}
 
void kol(tree *d,int *j,int m)
{   stack *s;
    s=NULL;
    tree *t;
    t=d;
    int f=1,n=-1;//k-предыдущий элемент стека,n-номер текущего уровня
    tree *k=NULL;
    while (f)
    {   while (t!=NULL&&n<m)
        {   in (&s,t);
            k=t;
            t=t->left;
            n++;
        }
        if(s!=NULL)
        {   if(n==m)
            {   out (&s,&t);
                *j=*j+1;
                if(s!=NULL)k=s->elem;
                t=NULL;
                n--;
            }
            else
            {   if(k->right!=NULL)
                {   if(m==n+1)
                    {   *j=*j+1;
                        out (&s,&t);
                        if(s!=NULL)k=s->elem;
                        t=NULL;
                        n--;
                    }
                    else
                    {   out (&s,&t);
                        t=t->right;
                    };
                }
                else
                {   out (&s,&t);
                    if(s!=NULL)k=s->elem;
                    t=NULL;
                    n--;
                };
            };
        }
        else    f=0;
    }
}
 
void main ()
{   setlocale(LC_CTYPE,"Russian");
    tree *d;
    FILE *file;
    int j=0,m=-1;//j-количесвто элементов на уровне,m-номер заданного уровня
    file =fopen("input.txt","r");
    d=build(file);
    fclose(file);
    printf("Введите номер уровня\n");
    scanf("%i",&m);
    kol(d,&j,m);
    printf("Количесвто элементов на %i уровне равно %i\n",m,j);
    _getch();
}
Yandex
Объявления
25.04.2011, 17:10     Бинарные деревья
Ответ Создать тему
Опции темы

Текущее время: 16:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru