Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.68/19: Рейтинг темы: голосов - 19, средняя оценка - 4.68
1 / 1 / 1
Регистрация: 13.09.2009
Сообщений: 96
1

Количество узлов на каждом уровне

29.04.2010, 01:42. Просмотров 3395. Ответов 12
Метки нет (Все метки)

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
#include <stdio.h>
#include <stdlib.h>
typedef struct item {
  int data;
  struct item *left;
  struct item *right;
} Item;
 
void AddNode(int data, Item **node);
 
void main(void)
{
  char buffer[128];
  int i;
  Item *root = NULL; 
  FILE *fp = fopen("ex52.txt", "r"); 
 
  if (!fp) exit(1); 
  
  while (fgets(buffer, 128, fp) != NULL)
    AddNode(atoi(buffer), &root); 
  fclose(fp);
  system("PAUSE");  
  return 0;
}
 
void AddNode(int data, Item **node)
{
  if (*node == NULL) {
    *node = (Item *)calloc(1, sizeof(Item));
    (*node)->data = data;
    (*node)->left = (*node)->right = NULL;
  } else {
    if (data < (*node)->data)
      AddNode(data, &(*node)->left);
    else if (data > (*node)->data)
      AddNode(data, &(*node)->right);
    else
      puts("There is such element in the tree");
  }
}
В текстовом файле записаны целые числа. Построить бинарное дерево поиска, в узлах которого хранятся числа из файла. Разработать функцию, определяющую число узлов дерева на
каждом уровне. С бинарным деревом все ок, но как написать эту функцию для определения кол-ва узлов на каждом уровне?(
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.04.2010, 01:42
Ответы с готовыми решениями:

Определить число узлов на каждом уровне дерева
Я не силен в деревьях, помогите пожалуйста

Вывод количества вершин(узлов) на заданном уровне
Напишите пожалуйста прогу которая будет выводить количество вершин(узлов) на уровне который вводим...

Определить количество узлов на каждом уровне данного бинарного дерева
Помогите с этой задачей) Определить количество узлов на каждом уровне данного бинарного дерева....

Определить число узлов на каждом уровне дерева
Помогите пожалуйста, нужно определить число узлов на каждом уровне дерева. За ранее спасибо.

12
221 / 135 / 48
Регистрация: 12.04.2010
Сообщений: 248
29.04.2010, 10:49 2
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int get(Item * node,int n,int c=0)
{
    if(n == c)  return 1;
    return ((node->left)?get(node->left,n,c+1):0) + ((node->right)?get(node->right,n,c+1):0);
}
 
void lvl(Node * root){
  int t = 0, l = 0;
  while((l = get(root, t++)) != 0){
      printf("lvl(%d) = %d\n", t, l);
  }
}
 
void main(void)
{
//.....
     lvl(root);
//......
}
Вот... как-то так
1
1 / 1 / 1
Регистрация: 13.09.2009
Сообщений: 96
29.04.2010, 15:49  [ТС] 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
#include <stdio.h>
#include <stdlib.h>
typedef struct item {
  int data;
  struct item *left;
  struct item *right;
} Item;
 
void AddNode(int data, Item **node);
int get(Item * node,int n,int c);
void lvl(Node * root);
 
int main(void)
{
  char buffer[128];
  int i;
  Item *root = NULL; 
  FILE *fp = fopen("ex52.txt", "r"); 
 
  if (!fp) exit(1); 
  
  while (fgets(buffer, 128, fp) != NULL)
    AddNode(atoi(buffer), &root); 
  fclose(fp);
  lvl(root);
  system("PAUSE");      
  return 0;
}
 
void AddNode(int data, Item **node)
{
  if (*node == NULL) {
    *node = (Item *)calloc(1, sizeof(Item));
    (*node)->data = data;
    (*node)->left = (*node)->right = NULL;
  } else {
    if (data < (*node)->data)
      AddNode(data, &(*node)->left);
    else if (data > (*node)->data)
      AddNode(data, &(*node)->right);
    else
      puts("There is such element in the tree");
  }
}
 
int get(Item * node,int n,int c)
{
        if(n == c)  return 1;
        return ((node->left)?get(node->left,n,c+1):0) + ((node->right)?get(node->right,n,c+1):0);
}
 
void lvl(Node * root){
  int t = 0, l = 0;
  while((l = get(root, t++)) != 0){
          printf("lvl(%d) = %d\n", t, l);
  }
}
Не компилится, ругается на функции(((
0
221 / 135 / 48
Регистрация: 12.04.2010
Сообщений: 248
29.04.2010, 15:55 4
Цитата Сообщение от inferno mf Посмотреть сообщение
Не компилится, ругается на функции(((
Как ругается? Сильно? Чего пишет-то?

C
1
int get(Item * node,int n,int c=0)
0
1 / 1 / 1
Регистрация: 13.09.2009
Сообщений: 96
29.04.2010, 16:30  [ТС] 5
Цитата Сообщение от uggway Посмотреть сообщение
Как ругается? Сильно? Чего пишет-то?

C
1
int get(Item * node,int n,int c=0)
Вот в этой строк например - syntax error before '*' token

C++
1
void lvl(Node * root);
0
221 / 135 / 48
Регистрация: 12.04.2010
Сообщений: 248
29.04.2010, 16:52 6
C
1
void lvl(Item * root);
..............................
1
1 / 1 / 1
Регистрация: 13.09.2009
Сообщений: 96
29.04.2010, 17:08  [ТС] 7
C++
1
while((l = get(root, t++)) != 0){
Теперь ругается на эту строчку...

too few arguments to function 'get'

Добавлено через 4 минуты
Цитата Сообщение от inferno mf Посмотреть сообщение
C++
1
while((l = get(root, t++)) != 0){
Теперь ругается на эту строчку...

too few arguments to function 'get'
эту исправил

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int get(Item * node,int n,int c)
{
    c=0;
        if(n == c)  return 1;
        return ((node->left)?get(node->left,n,c+1):0) + ((node->right)?get(node->right,n,c+1):0);
}
 
void lvl(Item * root){
  int t = 0, l = 0,c=0;
  while((l = get(root, t++,c++)) != 0){
          printf("lvl(%d) = %d\n", t, l);
  }
}
в файле чисел около 10-и, но отображает только 1-ый уровень, и то неверно(
0
221 / 135 / 48
Регистрация: 12.04.2010
Сообщений: 248
29.04.2010, 20:14 8
Ну блин... не знаю как еще написать...
НЕ ИСПРАВЛЯЙ ЭТУ СТРОЧКУ!
C
1
int get(Item * node,int n,int c=0)
......
Хотя если ты боишься такой записи, то исправь лучше
C
1
while((l = get(root, t++, 0)) != 0){
а в других местах не надо ничего менять
1
1 / 1 / 1
Регистрация: 13.09.2009
Сообщений: 96
29.04.2010, 20:40  [ТС] 9
Цитата Сообщение от uggway Посмотреть сообщение
Ну блин... не знаю как еще написать...
НЕ ИСПРАВЛЯЙ ЭТУ СТРОЧКУ!
C
1
int get(Item * node,int n,int c=0)
......
Хотя если ты боишься такой записи, то исправь лучше
C
1
while((l = get(root, t++, 0)) != 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
#include <stdio.h>
#include <stdlib.h>
typedef struct item {
  int data;
  struct item *left;
  struct item *right;
} Item;
 
void AddNode(int data, Item **node);
int get(Item * node,int n,int c);
void lvl(Item * root);
 
 
 
int main(void)
{
  char buffer[512];
  int i;
  Item *root = NULL; 
  FILE *fp = fopen("ex52.txt", "r"); 
 
  if (!fp) exit(1); 
  
  while (fgets(buffer, 512, fp) != NULL)
    AddNode(atoi(buffer), &root); 
  lvl(root);
  fclose(fp);
  /*lvl(root);*/
  system("PAUSE");      
  return 0;
}
 
void AddNode(int data, Item **node)
{
  if (*node == NULL) {
    *node = (Item *)calloc(1, sizeof(Item));
    (*node)->data = data;
    (*node)->left = (*node)->right = NULL;
  } else {
    if (data < (*node)->data)
      AddNode(data, &(*node)->left);
    else if (data > (*node)->data)
      AddNode(data, &(*node)->right);
    else
      puts("There is such element in the tree");
  }
}
int get(Item * node,int n,int c)
{
       c=0;
       if(n == c)  return 1;
        return ((node->left)?get(node->left,n,c+1):0) + ((node->right)?get(node->right,n,c+1):0);
}
 
void lvl(Item * root){
  int t = 0, l = 0;
    while((l = get(root, t++, 0)) != 0){
          printf("lvl(%d) = %d\n", t, l);
  }
}
Ее в любом случае придется изменить, т.к. компилятор ругается на занк равенства в скобках...

При таком коде, выдает всегда lvl 1 =1... В файле чисел около десятка.
0
221 / 135 / 48
Регистрация: 12.04.2010
Сообщений: 248
29.04.2010, 20:53 10
Ее в любом случае придется изменить, т.к. компилятор ругается на занк равенства в скобках...
Странно...
При таком коде, выдает всегда lvl 1 =1... В файле чисел около десятка.
Я ж написал: "БОЛЬШЕ НИЧЕГО НЕ МЕНЯТЬ"
У тебя в функции get написанно c = 0, поэтому и только один уровень может показать.
0
1 / 1 / 1
Регистрация: 13.09.2009
Сообщений: 96
29.04.2010, 21:01  [ТС] 11
Цитата Сообщение от uggway Посмотреть сообщение
Странно...

Я ж написал: "БОЛЬШЕ НИЧЕГО НЕ МЕНЯТЬ"
У тебя в функции get написанно c = 0, поэтому и только один уровень может показать.
Ясно, спасибо)
0
1 / 1 / 1
Регистрация: 13.09.2009
Сообщений: 96
05.05.2010, 00:36  [ТС] 12
Программа работает, но не уверен, что правильно...

В файле записаны такие числа: 1, 2,3,4,5

Результат : lvl<1> = 1 , lvl<2> = 2,lvl<3> = 1 , lvl<4> = 1 , lvl<5> = 1

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
#include <stdio.h>
#include <stdlib.h>
typedef struct item {
  int data;
  struct item *left;
  struct item *right;
} Item;
 
void AddNode(int data, Item **node);
int get(Item * node,int n,int c);
void lvl(Item * root);
 
 
 
int main(void)
{
  char buffer[512];
  int i;
  Item *root = NULL; 
  FILE *fp = fopen("ex52.txt", "r"); 
 
  if (!fp) exit(1); 
  
  while (fgets(buffer, 512, fp) != NULL)
    AddNode(atoi(buffer), &root); 
  lvl(root);
  fclose(fp);
  /*lvl(root);*/
  system("PAUSE");      
  return 0;
}
 
 void AddNode(int data, Item **node)
  {
  if (*node == NULL) {
    *node = (Item *)calloc(1, sizeof(Item));
    (*node)->data = data;
    (*node)->left = (*node)->right = NULL;
  } else {
    if (data < (*node)->data)
      AddNode(data, &(*node)->left);
    else if (data > (*node)->data)
      AddNode(data, &(*node)->right);
    else
      puts("There is such element in the tree");
  }
}
 int get(Item * node,int n,int c)
{
       if(n == c)  return 1;
        return ((node->left)?get(node->left,n,c+1):0) + ((node->right)?get(node->right,n,c+1):0);
}
 
 void lvl(Item * root){
  int t = 0, l = 0;
    while((l = get(root, t++, 0)) != 0){
          printf("lvl(%d) = %d\n", t, l);
  }
 }
0
221 / 135 / 48
Регистрация: 12.04.2010
Сообщений: 248
05.05.2010, 09:02 13
Твоя программа дает немного другой результат
lvl(1) = 1
lvl(2) = 1
lvl(3) = 1
lvl(4) = 1
lvl(5) = 1
Для проверки дерево строится на бумажке и считается вручную, т.е.
Код
         1                         1
           \
             2                     1
              \
                3                  1
                  \
                   4               1
                     \                
                      5            1
Можно взять другой набор
3 4 2 1 6 5 7
Код
           3                       1
          / \
         2   4                     2
        /      \
       1        6                  2
                / \
               5   7               2
lvl(1) = 1
lvl(2) = 2
lvl(3) = 2
lvl(4) = 2
Что и требовалось доказать
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.05.2010, 09:02

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Бинарные деревья. Найти количество узлов на n уровне
Коротко о программе. Дано бинарное дерево. Нужно нерекурсивно(через стеки) найти количество узлов...

Количество атомов на каждом уровне вложенности
Здравствуйте! Собственно, задача состоит в том, чтобы сформировать список следующего вида: ((lvl1...

Найти количество атомов многоуровневого списка на каждом уровне
Здравствуйте, нужна помощь, вот задание: Найти количество атомов списка с подсписков. Знаю что...

Определить количество листьев на каждом уровне дерева итеративным способом
Здравствуйте, необходима помощь. Необходимо написать процедуру, определяющую количество листьев на...

Бинарные деревья в списке: определить количество отрицательных узлов в каждом дереве
ребят, помогите доделать прогу, есть список, а в нем бинарные деревья, нужно чтобы она выводила мне...

Подсчет количества вершин на каждом уровне дерева
В общем я написал функцию, но что-то он считает неверно. Не могли бы вы мне помочь разобраться? ...


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

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

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