0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
1

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

03.02.2013, 18:42. Показов 5941. Ответов 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;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.02.2013, 18:42
Ответы с готовыми решениями:

Поиск количества совпадающих элементов в бинарном дереве
Здравствуйте. Нужно найти количество совпадающих элементов в бинарном дереве. Я написал следующие...

Функция поиска в бинарном дереве
Я понимаю как реализовать эту функцию если в бинарном дереве хранятся обычные числа(последовательно...

Необычная функция в бинарном дереве поиска
Здравствуйте, уважаемые форумчане. Очень прошу Вашей помощи. Задание: Реализовать структуру...

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

9
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 13:35  [ТС] 2
UP
0
353 / 338 / 101
Регистрация: 03.02.2013
Сообщений: 1,018
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;
}
1
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 14:01  [ТС] 4
Спасибо))) я так понял етот рекурсивный вариант?
0
353 / 338 / 101
Регистрация: 03.02.2013
Сообщений: 1,018
05.02.2013, 14:07 5
Цитата Сообщение от hokoko Посмотреть сообщение
Спасибо))) я так понял етот рекурсивный вариант?
да, это рекурсивный, а итеративный - это всякие обходы в ширину/высоту/глубину
больше кода и не так оптимально ) хотя может и есть какие-то варианты
0
Эксперт С++
5053 / 3114 / 271
Регистрация: 11.11.2009
Сообщений: 7,045
05.02.2013, 14:10 6
Цитата Сообщение от abit Посмотреть сообщение
больше кода и не так оптимально
Да ну? Рекурсия (т.е. постоянные вызовы функций и сохранения контекстов) - далеко не так оптимально, как итерация.
1
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 14:12  [ТС] 7
А можно еще итеративный пример на ету задачу?
0
353 / 338 / 101
Регистрация: 03.02.2013
Сообщений: 1,018
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);
}
на удивление даже работает)))
0
Эксперт С++
5053 / 3114 / 271
Регистрация: 11.11.2009
Сообщений: 7,045
05.02.2013, 14:53 9
Цитата Сообщение от abit Посмотреть сообщение
не сильно отличается
Ключевая фраза. Стек используют, но 1) не вызывают функцию и 2) не сохраняют контекст вызывающей функции. Плюс для большого дерева стек может переполниться, чего при итерации практически никогда не случится (работу с очень большими данными, которые в принципе в оперативную память не влезут, не рассматриваем).
0
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 15:54  [ТС] 10
Спасибо всем большое за примеры. Вы мне очень помогли.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.02.2013, 15:54
Помогаю со студенческими работами здесь

Функция: есть ли в бинарном дереве внутренний узел, у которого только один потомок?
Здравствуйте. Помогите пожалуйста. Надо написать функцию,проверяющую есть ли в дереве внутренний...

Алгоритм для подсчета количества элементов в дереве
Здравствуйте! Помогите придумать алгоритм для подсчета элементов в дереве. Например нужно...

Сумма элементов в бинарном дереве
Есть бинарное дерево поиска, в котором целочисленные значения. data BinarySearchTree = ...

Сумма элементов в бинарном дереве
Требуется реализовать функцию(void findSum(); ) которая определить сумму цифр в значениях тех...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru