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

Сумма чисел в бинарном дереве - C++

Восстановить пароль Регистрация
 
 
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 19:43     Сумма чисел в бинарном дереве #1
Выбрать уровень(глубину, высоту) бинарного дерева и посчитать сумму чисел(в вершинах), находящихся на этом уровне.
P.S. Дерево построено, выведено на экран и заполнено случайными числами.
Весь интернет перерыл и не нашел решения моей проблемы.
Если кто знает как это сделать-подскажите плз
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
UnsKneD
алкокодер
 Аватар для UnsKneD
153 / 149 / 11
Регистрация: 27.12.2012
Сообщений: 548
01.05.2013, 19:52     Сумма чисел в бинарном дереве #2
Troll1, для начала ваш код покажите.
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 19:54  [ТС]     Сумма чисел в бинарном дереве #3
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
     
typedef struct tree
{
    int n;
    tree *left;
    tree *right;
}tree;
     
 
tree *Insert(tree *root, int n)
{ 
    if (root == NULL)
    { 
        root = (tree*)malloc(sizeof(tree));
        root->n = n;
        root->left = root->right = NULL;
    }
    else
    { 
        if (n <= root->n) root->left = Insert(root->left, n);
        else root->right = Insert(root->right, n);
    }
 
    return root;
}
 
 
void OutputTree(tree *root, int totalSpace)
        {
            while(root != NULL)
            {
                OutputTree(root->right, totalSpace + 4);
 
                for(int i = 1; i<=totalSpace; i++)
                    printf(" ");
                    printf("%d\n", root -> n);
 
                root = root -> left;
                totalSpace += 4;
            }
        }
 
void DeleteTree(tree *root)
{
    if (root == 0) return;
    if (root->left) DeleteTree(root->left);
    if (root->right) DeleteTree(root->right);
    free(root);
}
 
int main()
{
    int i, sum;
    int totalSpace=0;
 
    srand (time(NULL)); 
    tree *mytree = NULL, *head_tree=NULL;
    for (i = 0; i<10; i++)
    {
        mytree = Insert(mytree, rand() % 50 + 1);
        if(i==0) head_tree=mytree; 
    }
    printf("Root: %d\n",head_tree->n);
    printf("Tree:\n");
    OutputTree(head_tree, 0);
    DeleteTree(head_tree);
    return 0;
 
}
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 780
Записей в блоге: 10
01.05.2013, 19:54     Сумма чисел в бинарном дереве #4
тебе нужно на определенном уровне
посчитать сумму элументов так ?
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 19:55  [ТС]     Сумма чисел в бинарном дереве #5
Qazan, Да. Пользователь вводит номер уровня, и получает сумму чисел.
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 780
Записей в блоге: 10
01.05.2013, 19:55     Сумма чисел в бинарном дереве #6
когда структуру создавал почему создал просто структуру а не указатель в самом классе
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 19:58  [ТС]     Сумма чисел в бинарном дереве #7
Qazan, На тот момент полагал, что так проще. Даже не задумывался об этом...
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 780
Записей в блоге: 10
01.05.2013, 20:02     Сумма чисел в бинарном дереве #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void sum(int &i, int &c,int &res)
{
   if (!root) 
   return;
   if (c == i)
  {
    res += root->info;
  }
  i++;
  sum(root -> left, i, c,res);
  sum(root -> right, i, c,res);
  i--;
}
Добавлено через 2 минуты
i - доп переменная знает в каком она сеичас уровне ( нач знач 0
c - номер уровня
res - ( сумма элементов нач знач 0
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 20:05  [ТС]     Сумма чисел в бинарном дереве #9
Спасибо. Но ваш код нифига не компилируется
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 780
Записей в блоге: 10
01.05.2013, 20:10     Сумма чисел в бинарном дереве #10
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void sum(tree* &root,int &i, int &c,int &res)
{
   if (!root) 
   return;
   if (c == i)
  {
    res += root->info;
  }
  i++;
  sum(root -> left, i, c,res);
  sum(root -> right, i, c,res);
  i--;
}
Добавлено через 2 минуты
i - доп переменная знает в каком она сеичас уровне ( нач знач 0
c - номер уровня
res - ( сумма элементов нач знач 0

Добавлено через 1 минуту
а теперь ?
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 20:38  [ТС]     Сумма чисел в бинарном дереве #11
Qazan,
Спасибо. Теперь пытаюсь включить его в программу так, чтобы пользователь вводил номер уровня, программа считывала, и в зависимости от уровня выводила на экран сумму. Может у Вас быстрее получится?)

Добавлено через 10 минут
Qazan, Смотрите, вот что я попробовал изобразить:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void sum(tree* &root,int &i, int &c,int &res)
{
   printf("Number of level:");
   scanf("%d",&c); 
   if (!root) 
   return;
   if (c == i)
  {
    res += root->n;
  }
  i++;
  sum(root -> left, i, c,res);
  sum(root -> right, i, c,res);
  i--;
  printf("Sum=%d", &res);
}
Добавлено через 11 минут
Но у меня нифига не получилось)
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 780
Записей в блоге: 10
01.05.2013, 20:56     Сумма чисел в бинарном дереве #12
ввод не нужно делать внутри функций, в тем более рекурсивной
сделай это перед вызовом функций

Добавлено через 300 лет
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
...
void sum(tree* &root,int &i, int &c,int &res)
{
   
   if (!root) 
   return;
   if (c == i)
  {
    res += root->n;
  }
  i++;
  sum(root -> left, i, c,res);
  sum(root -> right, i, c,res);
  i--;
  printf("Sum=%d", &res);
}
 
 
 
int main()
{
 int c;
  printf("Number of level:");
   scanf("%d",&c); 
  Tree * root = 0;
  // инициализируешь дерево 
  int i = 0,res = 0;
  sum(tree* &root,int &i, int &c,int &res)
  // здесь готовая сумма в res
 
 return 0;
}
Добавлено через 6 минут
ввод не нужно делать внутри функций, в тем более рекурсивной
сделай это перед вызовом функций

Добавлено через 300 лет
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
...
void sum(tree* &root,int &i, int &c,int &res)
{
   
   if (!root) 
   return;
   if (c == i)
  {
    res += root->n;
  }
  i++;
  sum(root -> left, i, c,res);
  sum(root -> right, i, c,res);
  i--;
 
}
 
 
 
int main()
{
 int c;
  printf("Number of level:");
   scanf("%d",&c); 
  Tree * root = 0;
  // инициализируешь дерево 
  int i = 0,res = 0;
  sum(root,i, c,res)
  // здесь готовая сумма в res
  printf("Sum=%d", res);
 return 0;
}
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 21:14  [ТС]     Сумма чисел в бинарном дереве #13
void sum как у тебя, а 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
int main()
{
    int i;
    int totalSpace=0;
 
    srand (time(NULL)); 
    tree *mytree = NULL, *head_tree=NULL;
    for (i = 0; i<10; i++)
    {
        mytree = Insert(mytree, rand() % 50 + 1);
        if(i==0) head_tree=mytree; 
    }
    printf("Root: %d\n",head_tree->n);
    printf("Tree:\n");
    OutputTree(head_tree, 0);
     int c;
  printf("Number of level:");
   scanf("%d",&c); 
  Tree * root = 0;
  // инициализируешь дерево 
  int i = 0,res = 0;
  sum(tree* &root,int &i, int &c, &res);
    DeleteTree(head_tree);
    return 0;
 
}
Добавлено через 1 минуту
не нравится такая строка:
C++
1
Tree * root = 0;
Добавлено через 6 минут
исправил

Добавлено через 8 минут
Вот код: Выводит сумму 0...
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
     
typedef struct tree
{
    int n;
    tree *left;
    tree *right;
}tree;
     
 
tree *Insert(tree *root, int n)
{ 
    if (root == NULL)
    { 
        root = (tree*)malloc(sizeof(tree));
        root->n = n;
        root->left = root->right = NULL;
    }
    else
    { 
        if (n <= root->n) root->left = Insert(root->left, n);
        else root->right = Insert(root->right, n);
    }
 
    return root;
}
 
 
void OutputTree(tree *root, int totalSpace)
        {
            while(root != NULL)
            {
                OutputTree(root->right, totalSpace + 4);
 
                for(int j = 1; j<=totalSpace; j++)
                    printf(" ");
                    printf("%d\n", root -> n);
 
                root = root -> left;
                totalSpace += 4;
            }
        }
 
void DeleteTree(tree *root)
{
    if (root == 0) return;
    if (root->left) DeleteTree(root->left);
    if (root->right) DeleteTree(root->right);
    free(root);
}
 
void sum(tree* &root,int &i, int &c,int &res)
{
   if (!root) 
   return;
   if (c == i)
  {
    res += root->n;
  }
  i++;
  sum(root -> left, i, c,res);
  sum(root -> right, i, c,res);
  i--;
  printf("Sum=%d", &res);
}
 
 
int main()
{
    int k;
    int totalSpace=0;
 
    srand (time(NULL)); 
    tree *mytree = NULL, *head_tree=NULL;
    for (k = 0; k<10; k++)
    {
        mytree = Insert(mytree, rand() % 50 + 1);
        if(k==0) head_tree=mytree; 
    }
    printf("Root: %d\n",head_tree->n);
    printf("Tree:\n");
    OutputTree(head_tree, 0);
    int c;
  printf("Number of level:");
   scanf("%d",&c); 
  tree * root = 0;
  // инициализируешь дерево 
  int i = 0,res = 0;
  sum(root,i, c,res);
  // здесь готовая сумма в res
  printf("Sum=%d", res);
    DeleteTree(head_tree);
    return 0;
 
}
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 780
Записей в блоге: 10
01.05.2013, 21:52     Сумма чисел в бинарном дереве #14
я для примера ))
убери зануление указателя перед вызовом функций для нахождения суммы ))


тебе нужно указатель на вершину дерева отправить ))
когда добавляешь элемент нужно сделать второй указатель который будет бегать ))_
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 21:57  [ТС]     Сумма чисел в бинарном дереве #15
Qazan, зануление убрал )
А вот с указателем не соображу
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 780
Записей в блоге: 10
01.05.2013, 22:20     Сумма чисел в бинарном дереве #16
а у тебя показ работает нормально?
что то он у тебя закрученный какоито

Добавлено через 28 секунд
Функция аутпут..
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 22:29  [ТС]     Сумма чисел в бинарном дереве #17
Qazan, Я его закрутил, чтобы на экран выводилось что-то на подобии дерева, а не строка из чисел
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 780
Записей в блоге: 10
01.05.2013, 22:41     Сумма чисел в бинарном дереве #18
Кинь скрин где выводит дерево как дерево ))
просто я до сих пор делал толшько через рекурсию ..
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 22:55  [ТС]     Сумма чисел в бинарном дереве #19
Смотрите:
[IMG]http://s16.***********/i191/1305/23/def3967bfde5.jpg[/IMG]

Добавлено через 36 секунд
Слева направо

Добавлено через 5 минут
Через рекурсию я тоже выводил, но в данной проге требуется именно видом дерева
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.05.2013, 23:28     Сумма чисел в бинарном дереве
Еще ссылки по теме:

Поиск дубликатов в бинарном дереве C++
C++ Поиск одинаковых элементов в бинарном дереве
C++ Разобраться в бинарном дереве

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

Или воспользуйтесь поиском по форуму:
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 780
Записей в блоге: 10
01.05.2013, 23:28     Сумма чисел в бинарном дереве #20
красава однако ))
Yandex
Объявления
01.05.2013, 23:28     Сумма чисел в бинарном дереве
Ответ Создать тему
Опции темы

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