0 / 0 / 0
Регистрация: 18.01.2012
Сообщений: 8

Бинарное дерево.Сумма ключей.

18.01.2012, 17:46. Показов 2398. Ответов 4
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте.Извините за слегка сумбурное описание проблемы,мне немного сложно говорить на русском.Столкнулся с такой проблемой.Дано бинарное дерево.Дано определение "путь"-сумма ключей от корня до узла без "сыновей".Например
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1

1 "путь" 5+4+11+7=27
2 "путь" 5+4+11+2=22
и т д
Нужно написать псевдо-код для рекурсивного алгоритма получающего дерево и некоторую сумму.Алгоритм возвращает true если в дереве существует "путь" равный этой сумме и false если нет такого "пути".Еще раз извините за корявое обьяснение.Буду благодарен теоретическому обьяснению как подойти к решению этой проблемы.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
18.01.2012, 17:46
Ответы с готовыми решениями:

Бинарное дерево
В полном бинарном дереве выполняется свойство: если номер узла i, то его потомки имеют номера 2i, 2i+1. Доказать это свойство. Подсказка -...

Бинарное дерево!!!!!
помогите пожалуйста решить задачу по бинарному дереву. Условие задания такое: создать структуру "бинарного дерева"...

Бинарное дерево без рекурсии
Здравствуйте! Таким образом, нужно 1) построить бинарное дерево 2) сделать post-order обход. Указано, что рекурсия запрещена. ...

4
Эксперт Java
 Аватар для turbanoff
4094 / 3828 / 745
Регистрация: 18.05.2010
Сообщений: 9,331
Записей в блоге: 12
18.01.2012, 20:08
элементы могу ты быть отрицательными?
0
0 / 0 / 0
Регистрация: 18.01.2012
Сообщений: 8
18.01.2012, 20:30  [ТС]
В условии этого не сказано.Предположим что да.
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
18.01.2012, 20:43
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
89
90
91
92
93
94
95
96
97
/////////////////////////////////////////////////////////////////////////////////////////
//Дано бинарное дерево. Дано определение "путь" - сумма ключей от корня до листа.
//Нужно написать псевдокод для рекурсивного алгоритма получающего дерево и 
//некоторую сумму.Алгоритм возвращает true если в дереве существует "путь" 
//равный этой сумме и false если нет такого "пути".
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_node
{
    int         key_;
    T_node*     L_;
    T_node*     R_;
    //-----------------------------------------------------------------------------------
    T_node(int  key)
        :
        key_    (key),
        L_      (),
        R_      ()
    {}
    //-----------------------------------------------------------------------------------
    void  L(int  key)
    {
        L_ = new   T_node(key);
    }
    //-----------------------------------------------------------------------------------
    void  R(int  key)
    {
        R_ = new   T_node(key);
    }
    //-----------------------------------------------------------------------------------
    bool  is_leaf()
    {
        return      L_ == 0
                &&  R_ == 0;
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
bool  tree_contains_way_with_key_sum
    (
        T_node*     tree,
        int         key_sum
    )
{    
    return      tree != 0
            &&  (
                    tree->is_leaf()
                            ?   key_sum == tree->key_ 
                            :       tree_contains_way_with_key_sum
                                        (
                                            tree->L_,
                                            key_sum - tree->key_
                                        )
 
                                ||  tree_contains_way_with_key_sum
                                        (
                                            tree->R_,
                                            key_sum - tree->key_
                                        )
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    T_node*  tree = new  T_node(5);
    tree    ->  L(4);   
    tree    ->  L_   ->  L(11);
    tree    ->  L_   ->  L_   ->  L(7);
    tree    ->  L_   ->  L_   ->  R(2);
    tree    ->  R(8);
    tree    ->  R_   ->  L(13);
    tree    ->  R_   ->  R(4);    
 
    for(;;)
    {
        std::cout << "Введите сумму ключей для поиска в дереве: ";
        int  key_sum = 0;
        std::cin >> key_sum;
 
        std::cout   <<  "Дерево "
                    <<  (
                            tree_contains_way_with_key_sum
                                (
                                    tree,
                                    key_sum
                                )
                                ? "содержит"
                                : "не содержит"
                        )
 
                    <<  " путь с заданной суммой ключей."
                    << std::endl
                    << std::endl
                    << std::endl;
    }
}
1
0 / 0 / 0
Регистрация: 18.01.2012
Сообщений: 8
18.01.2012, 20:58  [ТС]
Извините,я только начал учить С++,еще не могу разобрать ваш код досконально.Попробовал на С
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool Find_Path (Tree_Node *Node,int sum_to_find )
{
    bool Is_Path;
    Sum_to_find -= Node.Node_Value;
    if (sum_to_find == 0 && (Left== 0 && Right == 0))   Is_Path = true;
        else {
            if (Node.Left_Son!=0)
                {
                    Is_Path =   Find_Path (Node.Left_Son, sum_to_find);
                }
            if (Node.Right_Son!=0 &&  Is_Path != true)
                {
                    Is_Path = Find_Path (Node.Right_Son, sum_to_find);
                }
        }
    return Is_Path;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
18.01.2012, 20:58
Помогаю со студенческими работами здесь

Бинарное алфавитное дерево.Кодирование Ху-Таккера
Привет всем. Помогите реализовать алгоритм кодирования Ху-Таккера. Может у кого была подобная задача и остались исходники с кодом, скиньте...

Бинарное поисковое дерево. Максимальные пути
Помогите пожалуйста! Не знаю как реализовать одну функцию :( Есть задачка: Найти вершины, через которые проходят пути максимальной...

Ошибка в сравнении ключей .Бинарное дерево. Delphi
Всем доброго времени суток! Есть задача: построить АА-дерево поиска. Проблема в следующем. В теории создании я разобрался, но как...

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

Бинарное дерево, нахождение значения, замена, сумма
Добрый вечер! Недавно начал изучать пролог и забуксовал на задачке, в которой нужно написать три предиката для дерева: Бинарное...


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

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

Новые блоги и статьи
Отчёт о затраченных материалах за определенный период с макетом печатной формы
Maks 21.04.2026
Отчёт из решения ниже размещён в конфигурации КА2. Задача: показать затраченные материалы за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В качестве. . .
Отчёт о спецтехнике находящейся в ремонте
Maks 20.04.2026
Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .
Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)"
Hrethgir 19.04.2026
Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .
Запрет удаления строк ТЧ документа при определённом условии
Maks 19.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов
alhaos 17.04.2026
Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .
Мысли в слух. Про "навсегда".
kumehtar 16.04.2026
Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .
My Business CRM
MaGz GoLd 16.04.2026
Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .
Знаешь почему 90% людей редко бывают счастливыми?
kumehtar 14.04.2026
Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru