Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
0 / 0 / 0
Регистрация: 18.01.2012
Сообщений: 8

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

18.01.2012, 17:46. Показов 2335. Ответов 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
Ответ Создать тему
Новые блоги и статьи
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Нашел на реддите интересную статью под названием «Кто-нибудь знает, где получить бесплатный компьютер или. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru