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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
#1

Функция для нахождения количества элементов в бинарном дереве - C++

03.02.2013, 18:42. Просмотров 1574. Ответов 9
Метки нет (Все метки)

Помогите написать функцию для нахождения количества элементов в бинарном дереве. реализуйте функцию итеративно и рекурсивно.
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
#include <stack>
class Node
{ public:
int value;
Node* left;
Node* right;
};
int count(Node tree) { ... }
int main()
{
Node* root = new Node();
root>
left = new Node();
root>
left>
left = new Node();
root>
left>
right = new Node();
root>
left>
right>
right = new Node();
root>
right = new Node();
int result = count(root);
printf("%d\n", result);
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.02.2013, 18:42     Функция для нахождения количества элементов в бинарном дереве
Посмотрите здесь:
Необычная функция в бинарном дереве поиска C++
C++ Поиск одинаковых элементов в бинарном дереве
C++ Поиск одинаковых элементов в бинарном дереве.
Бинарный поиск для нахождения количества повторяющихся элементов C++
Массив: Написать программу для нахождения количества отрицательных элементов строки матрицы C++
Функция для нахождения уникальных элементов массива C++
C++ Функция для подсчета суммы и количества элементов больше K
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 13:35  [ТС]     Функция для нахождения количества элементов в бинарном дереве #2
UP
abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
05.02.2013, 13:43     Функция для нахождения количества элементов в бинарном дереве #3
Цитата Сообщение от hokoko Посмотреть сообщение
UP
не печальтесь )
C++
1
2
3
4
5
6
int count(Node * tree)
{
    if (tree == NULL)
        return 0;
    return count(tree->right) + count(tree->left) + 1;
}
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 14:01  [ТС]     Функция для нахождения количества элементов в бинарном дереве #4
Спасибо))) я так понял етот рекурсивный вариант?
abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
05.02.2013, 14:07     Функция для нахождения количества элементов в бинарном дереве #5
Цитата Сообщение от hokoko Посмотреть сообщение
Спасибо))) я так понял етот рекурсивный вариант?
да, это рекурсивный, а итеративный - это всякие обходы в ширину/высоту/глубину
больше кода и не так оптимально ) хотя может и есть какие-то варианты
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
05.02.2013, 14:10     Функция для нахождения количества элементов в бинарном дереве #6
Цитата Сообщение от abit Посмотреть сообщение
больше кода и не так оптимально
Да ну? Рекурсия (т.е. постоянные вызовы функций и сохранения контекстов) - далеко не так оптимально, как итерация.
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 14:12  [ТС]     Функция для нахождения количества элементов в бинарном дереве #7
А можно еще итеративный пример на ету задачу?
abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
05.02.2013, 14:52     Функция для нахождения количества элементов в бинарном дереве #8
Цитата Сообщение от silent_1991 Посмотреть сообщение
Да ну? Рекурсия (т.е. постоянные вызовы функций и сохранения контекстов) - далеко не так оптимально, как итерация.
продемонстрируйте нам код )
известные мне приёмы обхода (в глубину/ширину) во всю юзают стек, что по сути не сильно отличается от рекурсивного обхода

вот написал итеративный обход в ширину
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int count(Node * tree)
{
   unsigned int counter = 0;
   stack <Node*> st;
  do
  {
    while (tree != 0)
    {
      st.push(tree);
      tree = tree->left;
    }
    if (st.empty()) return counter-1;
    tree=st.top();
    st.pop();
    if ((tree->right == NULL))++counter;
    if (tree->left == NULL) ++counter;
    tree = tree->right;
  }
  while (true);
}
на удивление даже работает)))
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
05.02.2013, 14:53     Функция для нахождения количества элементов в бинарном дереве #9
Цитата Сообщение от abit Посмотреть сообщение
не сильно отличается
Ключевая фраза. Стек используют, но 1) не вызывают функцию и 2) не сохраняют контекст вызывающей функции. Плюс для большого дерева стек может переполниться, чего при итерации практически никогда не случится (работу с очень большими данными, которые в принципе в оперативную память не влезут, не рассматриваем).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.02.2013, 15:54     Функция для нахождения количества элементов в бинарном дереве
Еще ссылки по теме:
Строки в бинарном дереве C++
Предок в бинарном дереве C++
Поиск в Бинарном Дереве! C++
C++ Разобраться в бинарном дереве
C++ Удалить узел в бинарном дереве

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

Или воспользуйтесь поиском по форуму:
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 15:54  [ТС]     Функция для нахождения количества элементов в бинарном дереве #10
Спасибо всем большое за примеры. Вы мне очень помогли.
Yandex
Объявления
05.02.2013, 15:54     Функция для нахождения количества элементов в бинарном дереве
Ответ Создать тему
Опции темы

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