Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
Juvenis
0 / 0 / 0
Регистрация: 09.01.2017
Сообщений: 36
1

Подсчет вершин в бинарном дереве

20.03.2017, 06:31. Просмотров 1168. Ответов 3
Метки нет (Все метки)

Здравствуйте,помогите написать функцию ,которая подсчитывает число вершин на N-ом уровне бинарного дерева T(корень считать вершиной 0-го уровня)
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.03.2017, 06:31
Ответы с готовыми решениями:

Строки в бинарном дереве
Есть шаблонный класс бинарного дерева. Со числами он работает нормально, но при добавлении строки в...

Разобраться в бинарном дереве
Нашел вот такой вариант построения бинарного дерева. Просьба прокомментировать строки кода...

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

Поиск в бинарном дереве
Привет всем! Нужно написать код, с которым в бинарном дереве можно найти заданное пользователем...

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

3
ValeryLaptev
Эксперт С++
1055 / 834 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
20.03.2017, 07:03 2
Открываешь книжку, и читаешь: обход дерева.
Тебе нужен inorder -сначала корень, потом левый сосед, потом правый.
Функция - из 3 строчек.
Не поленись, посмотри сам.
0
Juvenis
0 / 0 / 0
Регистрация: 09.01.2017
Сообщений: 36
20.03.2017, 08:53  [ТС] 3
Я понимаю как происходит обход,но в данной задаче мне необходимо задать уровень и только потом считать количество вершин
0
Геомеханик
798 / 602 / 939
Регистрация: 26.06.2015
Сообщений: 1,409
20.03.2017, 11:11 4
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
#include <iostream>
 
struct node {
    node* left;
    node* right;
    int   val;
};
void tree_add(node*& tr, int val);
void tree_clear(node* tr);
int  tree_height(const node* tr);
int  tree_count(std::ostream& _out, const node* tr, int level, int i = 0);
 
int main(void){
    node* tr = NULL;
/*
   5, 7, 9, 6, 3, 2, 4
 
             5
           /   \
          3     7
         / \   / \ 
        2  4 6   9
*/
    int a[] = { 5, 7, 9, 6, 3, 2, 4 };
    int n   = sizeof(a)/sizeof(a[0]);
    for(int i = 0; i < n; ++i)
        tree_add(tr, a[i]);
 
    const int N = tree_height(tr);
    for(int l = 0; l < N; ++l){
        std::cout << l << "). ";
        int m = tree_count(std::cout, tr, l);
        std::cout << std::endl << "count elements: " << m << std::endl << std::endl;
    }
    tree_clear(tr);
    return 0;
}
 
//подсчёт кол-во элементов на определённом уровне
int tree_count(std::ostream& _out, const node* tr, int level, int i){
    int n = 0;
    if(tr != NULL){
        if(i == level){
            ++n;
            _out << tr->val << ' ';
        }
 
        if(tr->left != NULL)
            n += tree_count(_out, tr->left,  level, i + 1);
        if(tr->right != NULL)
            n += tree_count(_out, tr->right, level, i + 1);
    }
    return n;
}
 
//высота дерева
int tree_height(const node* tr){
    int l, r;
    if(tr != NULL){
        l = (tr->left  != NULL) ? tree_height(tr->left)  : 0;
        r = (tr->right != NULL) ? tree_height(tr->right) : 0;
        return ((l > r) ? l : r) + 1;
    }
    return 0;
}
 
//добавление
void tree_add(node*& tr, int val){
    if(tr == NULL){
        tr = new node();
        tr->val  = val;
        tr->left = tr->right = NULL;
    } else if(val < tr->val)
        tree_add(tr->left, val);
    else if(val > tr->val)
        tree_add(tr->right, val);
}
 
//удаление
void tree_clear(node* tr){
    if(tr != NULL){
        if(tr->left != NULL)
            tree_clear(tr->left);
        if(tr->right != NULL)
            tree_clear(tr->right);
        delete tr;
    }
}
0
20.03.2017, 11:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2017, 11:11

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

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

Сумма чисел в бинарном дереве
Выбрать уровень(глубину, высоту) бинарного дерева и посчитать сумму чисел(в вершинах), находящихся...


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

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

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