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

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

Войти
Регистрация
Восстановить пароль
 
element_1417
0 / 0 / 0
Регистрация: 16.04.2012
Сообщений: 5
#1

Рекурсивные деревья - C++

27.04.2012, 15:21. Просмотров 596. Ответов 2
Метки нет (Все метки)

День добрый.
Очень нужна помощь в решении задачи:

Найти все поддеревья, структура которых совпадает с заданной.

Ввод/Создание/Вывод/...дерева написать труда не составило.
С рекурсией и прочим тоже никаких вопросов.
А вот с основным заданием возникла проблема.
Как я понимаю, нужно сравнивать количество сыновей введённой структуры и исходного дерева, перемещаясь сверху-вниз по исходному. Но элементарно не могу написать код. Но элементарно не могу это запрограммировать.
Может быть, чем поможете.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2012, 15:21     Рекурсивные деревья
Посмотрите здесь:

C++ рекурсивные функции
РЕКУРСИВНЫЕ АЛГОРИТМЫ C++
рекурсивные функции C++
C++ рекурсивные функции
C++ Рекурсивные алгоритмы
Рекурсивные алгоритмы C++
C++ рекурсивные алгоритмы
C++ Рекурсивные и не рекурсивные функции (вычисление суммы всех натуральных чисел от 1 до n)
Рекурсивные функции C++
Рекурсивные функции C++
C++ Рекурсивные Деревья
C++ рекурсивные алгоритмы

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
element_1417
0 / 0 / 0
Регистрация: 16.04.2012
Сообщений: 5
04.05.2012, 21:54  [ТС]     Рекурсивные деревья #2
Неужели никто ничем помочь не может?
rst256
0 / 0 / 0
Регистрация: 16.04.2016
Сообщений: 3
18.03.2017, 19:48     Рекурсивные деревья #3
А в чем конкретно проблема то, если
Цитата Сообщение от element_1417 Посмотреть сообщение
С рекурсией и прочим тоже никаких вопросов.
?
Просто сделай внутри рекурсивного обхода узлов дерева сравнение его узлов с эталоном, если будет несовпадение на корневом узле эталона делай тогда сравнение узла с корнем эталона. Если будет совпадение и узел эталона корневой значит под-узел найден.
Вот пример кода на си:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int check_eq_root(tree_node * current_node, tree_node * match_node, tree_node * match_node_root){
    if( current_node->value==match_node->value && 
        check_eq(current_node->left, match_node->left, match_node_root) &&
        check_eq(current_node->rigth, match_node->rigth, match_node_root) &&
        . . .
        check_eq(current_node->some, match_node->some, match_node_root) 
    ){ // если текущий узел и его подузлы соответствуют текущему узлу эталона, тогда ...
        if( match_node==match_node_root ) // если при этом текущий узел эталона корневой, тогда ... 
            printf("node found: %p\n", current_node); // поддерево найдено. (возвр. значение при этом роли не играет).
        return 1; 
    }else{
        if( match_node!=match_node_root ) // если текущий узел эталона НЕ корневой, тогда ... 
            check_eq(current_node, match_node_root, match_node_root); // сравниваем текущий узел с корневым эталона
        return 0; // в не зависимости от сравнения с корневым эталона результат 0 (false).
    }
}
Yandex
Объявления
18.03.2017, 19:48     Рекурсивные деревья
Ответ Создать тему
Опции темы

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