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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
inferno mf
1 / 1 / 0
Регистрация: 13.09.2009
Сообщений: 96
29.04.2010, 01:42     Количество узлов на каждом уровне #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
#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");
  }
}
В текстовом файле записаны целые числа. Построить бинарное дерево поиска, в узлах которого хранятся числа из файла. Разработать функцию, определяющую число узлов дерева на
каждом уровне. С бинарным деревом все ок, но как написать эту функцию для определения кол-ва узлов на каждом уровне?(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.04.2010, 01:42     Количество узлов на каждом уровне
Посмотрите здесь:

C++ Известны оценки по физике каждого ученика двух классов.Определить средниюю оценку в каждом классе.Количество учащихся в каждом классе одинаковое!
C++ Дан текстовый файл. Вывести на экран количество предложений в нём и количество слов в каждом предложении.
C++ Дан текстовый файл. Вывести на экран количество предложений в нём и количество слов в каждом предложении
Вывод количества вершин(узлов) на заданном уровне C++
C++ Определить число листьев на каждом уровне дерева
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
uggway
219 / 133 / 9
Регистрация: 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);
//......
}
Вот... как-то так
inferno mf
1 / 1 / 0
Регистрация: 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);
  }
}
Не компилится, ругается на функции(((
uggway
219 / 133 / 9
Регистрация: 12.04.2010
Сообщений: 248
29.04.2010, 15:55     Количество узлов на каждом уровне #4
Цитата Сообщение от inferno mf Посмотреть сообщение
Не компилится, ругается на функции(((
Как ругается? Сильно? Чего пишет-то?

C
1
int get(Item * node,int n,int c=0)
inferno mf
1 / 1 / 0
Регистрация: 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);
uggway
219 / 133 / 9
Регистрация: 12.04.2010
Сообщений: 248
29.04.2010, 16:52     Количество узлов на каждом уровне #6
C
1
void lvl(Item * root);
..............................
inferno mf
1 / 1 / 0
Регистрация: 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-ый уровень, и то неверно(
uggway
219 / 133 / 9
Регистрация: 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){
а в других местах не надо ничего менять
inferno mf
1 / 1 / 0
Регистрация: 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... В файле чисел около десятка.
uggway
219 / 133 / 9
Регистрация: 12.04.2010
Сообщений: 248
29.04.2010, 20:53     Количество узлов на каждом уровне #10
Ее в любом случае придется изменить, т.к. компилятор ругается на занк равенства в скобках...
Странно...
При таком коде, выдает всегда lvl 1 =1... В файле чисел около десятка.
Я ж написал: "БОЛЬШЕ НИЧЕГО НЕ МЕНЯТЬ"
У тебя в функции get написанно c = 0, поэтому и только один уровень может показать.
inferno mf
1 / 1 / 0
Регистрация: 13.09.2009
Сообщений: 96
29.04.2010, 21:01  [ТС]     Количество узлов на каждом уровне #11
Цитата Сообщение от uggway Посмотреть сообщение
Странно...

Я ж написал: "БОЛЬШЕ НИЧЕГО НЕ МЕНЯТЬ"
У тебя в функции get написанно c = 0, поэтому и только один уровень может показать.
Ясно, спасибо)
inferno mf
1 / 1 / 0
Регистрация: 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);
  }
 }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.05.2010, 09:02     Количество узлов на каждом уровне
Еще ссылки по теме:

Определить количество слов в заданном тексте и количество символов в каждом слове C++
Просуммировать количество точек в наборе домино, где количество точек на каждом конце может быть от 1 до n C++
C++ Создание бинарного дерева и ограничение на количество узлов в ней

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

Или воспользуйтесь поиском по форуму:
uggway
219 / 133 / 9
Регистрация: 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
Что и требовалось доказать
Yandex
Объявления
05.05.2010, 09:02     Количество узлов на каждом уровне
Ответ Создать тему
Опции темы

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