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

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

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

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

03.02.2013, 18:42. Просмотров 1617. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.02.2013, 18:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Функция для нахождения количества элементов в бинарном дереве (C++):

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

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

Поиск одинаковых элементов в бинарном дереве - C++
Нужно вывести на экран все повторяющиеся элементы в бинарном дереве. # include &lt;iostream&gt; # include &lt;conio.h&gt; using namespace...

Поиск одинаковых элементов в бинарном дереве. - C++
Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента. Вывести на экран все одинаковые элементы в...

Бинарный поиск для нахождения количества повторяющихся элементов - C++
Здравствуйте. Стоит следующая несложная задача: Дан массив (отсортированный). Например 1 1 1 4 5 6 6 6 6 6 6 6 При вводе...

Массив: Написать программу для нахождения количества отрицательных элементов строки матрицы - C++
Здравствуйте. Нужна очень помощь. Задана числовая матрица А. Написать программу для нахождения количества отрицательных элементов строки...

9
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 13:35  [ТС] #2
UP
0
abit
264 / 263 / 33
Регистрация: 03.02.2013
Сообщений: 734
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;
}
0
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 14:01  [ТС] #4
Спасибо))) я так понял етот рекурсивный вариант?
0
abit
264 / 263 / 33
Регистрация: 03.02.2013
Сообщений: 734
05.02.2013, 14:07 #5
Цитата Сообщение от hokoko Посмотреть сообщение
Спасибо))) я так понял етот рекурсивный вариант?
да, это рекурсивный, а итеративный - это всякие обходы в ширину/высоту/глубину
больше кода и не так оптимально ) хотя может и есть какие-то варианты
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
05.02.2013, 14:10 #6
Цитата Сообщение от abit Посмотреть сообщение
больше кода и не так оптимально
Да ну? Рекурсия (т.е. постоянные вызовы функций и сохранения контекстов) - далеко не так оптимально, как итерация.
1
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 14:12  [ТС] #7
А можно еще итеративный пример на ету задачу?
0
abit
264 / 263 / 33
Регистрация: 03.02.2013
Сообщений: 734
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
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
05.02.2013, 14:53 #9
Цитата Сообщение от abit Посмотреть сообщение
не сильно отличается
Ключевая фраза. Стек используют, но 1) не вызывают функцию и 2) не сохраняют контекст вызывающей функции. Плюс для большого дерева стек может переполниться, чего при итерации практически никогда не случится (работу с очень большими данными, которые в принципе в оперативную память не влезут, не рассматриваем).
0
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
05.02.2013, 15:54  [ТС] #10
Спасибо всем большое за примеры. Вы мне очень помогли.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.02.2013, 15:54
Привет! Вот еще темы с ответами:

Функция для нахождения уникальных элементов массива - C++
Есть функция на JS, которой передается двумерный символьный массив. Она возвращает символы без повторений: function getLetters(a) { ...

Двоичное дерево поиска: подсчет количества элементов в дереве - C++
Помогите написать программу. Описать структуры данных, процедуры и функции, необходимые для работы с двоичными деревьями. Пользуясь этими...

Функция для подсчета суммы и количества элементов больше K - C++
Добрый вечер! Есть задачка одна - звучит так: С помощью генератора случайных чисел сформировать квадратную матрицу вещественных чисел...

Строки в бинарном дереве - C++
Есть шаблонный класс бинарного дерева. Со числами он работает нормально, но при добавлении строки в соответствующий объект этого класса на...


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

Или воспользуйтесь поиском по форуму:
10
Yandex
Объявления
05.02.2013, 15:54
Ответ Создать тему
Опции темы

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