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

Определить число листьев на каждом уровне дерева

13.06.2014, 05:15. Просмотров 3452. Ответов 2
Метки нет (Все метки)

Нужно составить такую функцию.
Именно на каждом отдельном уровне, а не по дереву вообще.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.06.2014, 05:15
Ответы с готовыми решениями:

Определить число листьев на каждом уровне бинарного дерева
Помогите! Нужно написать программу Определение число листьев на каждом уровне БИНАРНОГО дерева....

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

Подсчитать количество листьев дерева не на последнем уровне, имеющем листья.
Добрый день! Не могу разобраться со следующим: нужно подсчитать количество листьев не на последнем...

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

2
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
13.06.2014, 08:41 2
Лучший ответ Сообщение было отмечено Metavice как решение

Решение

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
119
120
121
122
123
#pragma comment(linker, "/STACK:167177216")
 
#include <stdio.h>
#include <stack>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <memory.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <time.h>
#include <cassert>
#include <cstring>
//#include <unordered_set>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define x first
#define y second
 
typedef long long li;
typedef long double ld;
typedef unsigned long long uli;
 
const int INF = 1e9;
const ld eps = 1e-9;
const li MOD = (li)(4e6 + 37);
const li INF64 = (li)(INF) * (li)(INF);
 
const int ddx[] = {-1, 1, 1, -1};
const int ddy[] = {1, 1, -1, -1};
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dxh[] = {-1, -1, -1, 1, 1, 1, 1, -1};
const int dyh[] = {1, -1, -1, -1, -1, 1, 1, 1};
const string dirs[] = {"RIGHT", "UP", "LEFT", "DOWN"};
 
const int N = 1000;
 
vector<int> g[N]; //spiski smezhnosti dereva
bool used[N]; //poseshali vershinu ili net
int depth[N]; //massiv glubin depth[i] == glubina vershini i
int max_deep = 0; // max glubina v dereve
int n; //kolichestvo vershin v dereve i kolichestvo reber
 
 
//poisk v glubinu: prinimaet vershinu i ee glubinu
void dfs(int v, int deep)
{
    used[v] = true;
    depth[v] = deep;
    max_deep = max(max_deep, deep);
    
    for(int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i];
        if(!used[to])
        {
            used[to] = true;
            dfs(to, deep + 1);
        }
    }
}
 
//sama funkciya
//type idet po vsem vershinam i esli glubina vershini ravna trebuemoy i vershina list(u nee tolko 1 rebro) to uvelichivaet otvet
 
int cnt(int deep)
{
    if(deep < 1 || deep > max_deep)
        return 0;
    if(deep == 1)
        return 0;
    
    int res = 0;
 
    for(int i = 1; i <= n; i++)
        if(depth[i] == deep && g[i].size() == 1)
            res++;
 
    return res;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //freopen("errors.txt", "w", stderr);
    //ios_base::sync_with_stdio(false);
    
 
    cin >> n;
    for(int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
 
    //cout << "777" << endl;
 
    dfs(1, 1);
 
    //cout << "WTF" << endl;
 
    for(int i = 1; i <= max_deep; i++)
    {
        cout << "kolichestvo list'ev na glubine " << i << " == " << cnt(i) << endl;
    }
 
    return 0;
}
http://pastebin.com/Kaex3huQ

ну вообще непонятно как именно должна выглядесть функция, просто можно заранее все насчитать, а функция будет просто брать ответ и возращать его, но я там написал, чтобы функция все считала!
0
0 / 0 / 0
Регистрация: 13.06.2014
Сообщений: 11
16.06.2014, 01:39  [ТС] 3
SlavaSSU, спасибо за ответ!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.06.2014, 01:39

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

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

Определить число листьев дерева
Дерево формировать динамически. Заполнить двоичное дерево следующим образом: если число меньше или...

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

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


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

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

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