Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
#1

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

01.05.2013, 19:43. Просмотров 1363. Ответов 20
Метки нет (Все метки)

Выбрать уровень(глубину, высоту) бинарного дерева и посчитать сумму чисел(в вершинах), находящихся на этом уровне.
P.S. Дерево построено, выведено на экран и заполнено случайными числами.
Весь интернет перерыл и не нашел решения моей проблемы.
Если кто знает как это сделать-подскажите плз
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.05.2013, 19:43
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Сумма чисел в бинарном дереве (C++):

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

Строки в бинарном дереве - C++
Есть шаблонный класс бинарного дерева. Со числами он работает нормально, но при добавлении строки в соответствующий объект этого класса на...

Разобраться в бинарном дереве - C++
Нашел вот такой вариант построения бинарного дерева. Просьба прокомментировать строки кода которые выделил ниже: #include...

Поиск в Бинарном Дереве! - C++
Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента. Вывести на экран все одинаковые элементы в...

Поиск дубликатов в бинарном дереве - C++
Требуется создать функцию поиска дубликатов ИНФОРМАЦИОННОЙ ЧАСТИ, НЕ КЛЮЧА в бинарном дереве. Ничего похожего в гугле и здесь на...

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

20
UnsKneD
алкокодер
155 / 151 / 12
Регистрация: 27.12.2012
Сообщений: 550
01.05.2013, 19:52 #2
Troll1, для начала ваш код покажите.
0
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;
 
}
0
Qazan
213 / 61 / 9
Регистрация: 30.04.2013
Сообщений: 835
Записей в блоге: 10
01.05.2013, 19:54 #4
тебе нужно на определенном уровне
посчитать сумму элументов так ?
0
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 19:55  [ТС] #5
Qazan, Да. Пользователь вводит номер уровня, и получает сумму чисел.
0
Qazan
213 / 61 / 9
Регистрация: 30.04.2013
Сообщений: 835
Записей в блоге: 10
01.05.2013, 19:55 #6
когда структуру создавал почему создал просто структуру а не указатель в самом классе
0
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 19:58  [ТС] #7
Qazan, На тот момент полагал, что так проще. Даже не задумывался об этом...
0
Qazan
213 / 61 / 9
Регистрация: 30.04.2013
Сообщений: 835
Записей в блоге: 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
0
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 20:05  [ТС] #9
Спасибо. Но ваш код нифига не компилируется
0
Qazan
213 / 61 / 9
Регистрация: 30.04.2013
Сообщений: 835
Записей в блоге: 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 минуту
а теперь ?
0
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 минут
Но у меня нифига не получилось)
0
Qazan
213 / 61 / 9
Регистрация: 30.04.2013
Сообщений: 835
Записей в блоге: 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;
}
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;
 
}
0
Qazan
213 / 61 / 9
Регистрация: 30.04.2013
Сообщений: 835
Записей в блоге: 10
01.05.2013, 21:52 #14
я для примера ))
убери зануление указателя перед вызовом функций для нахождения суммы ))


тебе нужно указатель на вершину дерева отправить ))
когда добавляешь элемент нужно сделать второй указатель который будет бегать ))_
0
Troll1
1 / 1 / 1
Регистрация: 23.09.2012
Сообщений: 91
01.05.2013, 21:57  [ТС] #15
Qazan, зануление убрал )
А вот с указателем не соображу
0
01.05.2013, 21:57
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.05.2013, 21:57
Привет! Вот еще темы с ответами:

Оператор присвоения в бинарном дереве - C++
Не смог разобраться. Прокомментируйте, будьте добры. Задание такое, определите стандартный конструктор и функции управления...

Удалить узел в бинарном дереве - C++
Добрый вечер. В задании нужно найти узел дерева с наибольшим показателем счетчика, после чего удалить найденный узел из дерева. В структуре...

Количество листьев в бинарном дереве - C++
Задача: Найти количество листьев в дереве. Собственно ввод и вывод дерева есть: #include &lt;iostream.h&gt; #include &lt;iomanip.h&gt; ...

Функция поиска в бинарном дереве - C++
Я понимаю как реализовать эту функцию если в бинарном дереве хранятся обычные числа(последовательно сравниваем и двигаемся по дереву в...


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

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

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