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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
wtfdotka
0 / 0 / 0
Регистрация: 25.12.2011
Сообщений: 12
#1

Работа с деревьями (Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева) - C++

22.03.2013, 15:58. Просмотров 1210. Ответов 7
Метки нет (Все метки)

Есть задача:
Дано N-дерево. Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева.
Дайте советы по алгоритму решения, допустим прохожу дерево, нахожу лист, который в заданном диапозоне, как дальше вывести все поддеревья с этим листом, имея, например, сейчас только указатель на этот лист?Можно ли все это сделать за один обход дерева? Или как сократить количество обходов? Помогите советом

Добавлено через 18 часов 54 минуты
Никакого совета не может дать?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2013, 15:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Работа с деревьями (Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева) (C++):

Удалить из массива все элементы значения которых находятся в заданном промежутке - C++
Уплотните массив, удалив из него все элементы, значение которых находится в заданном промежутке . Помогите пожалуйста

Найти все простые числа в заданном диапазоне - C++
Найти все простые числа в промежутке между натуральными числами а и b (а > 2000, b - а ≥ 20)

Найти все «пифагоровы тройки» в заданном диапазоне чисел - C++
Необходимо найти все «пифагоровы тройки» в заданном диапазоне чисел — натуральные решения уравнения x2+y2=k2, где x, y и k лежат в...

Найти все простые числа в заданном диапазоне и вывести их на экран - C++
Доброго времени суток! Есть задачка, есть кривое решение. :) Суть задачки такова: найти все простые числа до 1000 и вывести их на...

В заданном диапазоне чисел найти все сочетания цифр без повторений - C++
Доброго времени суток! Помогите исправить код программы.Вот задание: Для заданных m и n найти все сочетания по m из чисел 1,2,...,n, без...

Найти все числа в заданном диапазоне, которые делятся на любую из своих цифр - C++
Без понятий как сделать обясните плиз

7
fjay69
85 / 85 / 1
Регистрация: 26.10.2012
Сообщений: 248
22.03.2013, 16:05 #2
Попробую проиллюстрировать. Вот дерево. У него есть поддеревья. На концах поддеревьев есть листья.
Зеленым выделил искомые поддеревья. Должно быть так?
0
Миниатюры
Работа с  деревьями (Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева)  
wtfdotka
0 / 0 / 0
Регистрация: 25.12.2011
Сообщений: 12
22.03.2013, 16:19  [ТС] #3
Возможно я не знаю правильного определения поддерева и листа, но, например, поддерево корня, имеет лист в диапозоне, опускаемся ниже, тоже поддерево и оно тоже может иметь лист в диапозоне. Или я не правильно мыслил с самого начала?
0
fjay69
85 / 85 / 1
Регистрация: 26.10.2012
Сообщений: 248
22.03.2013, 16:25 #4

Вы сначала чётко сформулируйте задачу, а уж потом спрашивайте советов. Мы не телепаты.
0
wtfdotka
0 / 0 / 0
Регистрация: 25.12.2011
Сообщений: 12
22.03.2013, 16:38  [ТС] #5
Задача четко сформулирована в первом посте, я так же как и вы пытаюсь понять ее условие. Если смотреть во вашему рисунку, но алгоритм примерно такой? проходим дерево до уровня Нижняя граница -1 и проверяем условие не являются ли какой из сыновей узла листом?Только еще вопрос, как обознать поддерево с си? Нужно найти узел, сын которого лист, но тогда будут другие ветви или нужно найти ветвь, как вы указали на рисунке, то я не знаю как это обозначить, указатель на узел и указатель на сына-листа?
0
fjay69
85 / 85 / 1
Регистрация: 26.10.2012
Сообщений: 248
22.03.2013, 16:47 #6
Ладно, попробуем так.
Есть класс Tree. Объект класса Tree содержит переменную Name типа char, указатель на массив объектов Subtrees класса Tree и указатель на массив объектов Leafs класса Leaf. Объект класса Leaf содержит переменную Height типа int.
Класс Tree содержит методы, которые перебирают элементы массивов Subtrees и Leafs. Когда значение Height объекта класса Leaf будет соответствовать условиям, вывести имя объекта класса Tree, содержащий этот лист.
Алсо, чтобы задача имела практическое значение, нужны методы, с помощью которых можно перемещаться по деревьям и создавать/удалять/изменять деревья/листья
1
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
24.03.2013, 07:22 #7
Цитата Сообщение от wtfdotka Посмотреть сообщение
листья которых находятся в заданном диапазоне высот от корня поддерева.
Вообще-то расстояние от корня дерева называется уровнем.
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
/////////////////////////////////////////////////////////////////////////////////////////
//Дано N-дерево. Найти все поддеревья, листья которых находятся в заданном диапазоне уровней от корня поддерева.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <functional>
#include <iostream>
#include <set>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
class   T_node;
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<T_node*>    T_children_pointers;
typedef std::set<int>           T_node_heights_set;
typedef std::complex<int>       T_levels_segment;
/////////////////////////////////////////////////////////////////////////////////////////
class  T_node
{
    //-----------------------------------------------------------------------------------
    int                     node_ID_;
 
    T_node_heights_set      node_heights_set_;
    T_children_pointers     children_pointers_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_node(int  node_ID)
        :
        node_ID_(node_ID)
    {}
    //-----------------------------------------------------------------------------------
    bool  to_node_with_ID_add_child_with_ID
        (
            int     node_ID,
            int     child_ID
        )
    {
        bool    bool_res    =   false;
        if(node_ID_ == node_ID)
        {
            children_pointers_.push_back
                (
                    new     T_node(child_ID)
                );
 
            bool_res    =   true;
        }
        else
        {
            for (
                    T_children_pointers::iterator     child_pointer_it  =   children_pointers_.begin    ();
                    child_pointer_it                                    !=  children_pointers_.end      ();
                    ++child_pointer_it
                )
            {
                bool_res    =   (*child_pointer_it)->to_node_with_ID_add_child_with_ID
                                    (
                                        node_ID,
                                        child_ID
                                    );
 
                if( bool_res )
                {
                    break;
                }
            }
        }//else
        return  bool_res;
    }
    //-----------------------------------------------------------------------------------
    void  calc_min_and_max_leaf_levels_and_print_if_they_belongs_to_segment
        (
            int  min_allowable_max_leaf_level,
            int  max_allowable_max_leaf_level
        )
    {
        if  (
                !children_pointers_.empty()
            )
        {
            for (
                    T_children_pointers::const_iterator     child_pointer_it    =   children_pointers_.begin    ();
                    child_pointer_it                                            !=  children_pointers_.end      ();
                    ++child_pointer_it
                )
            {
                (*child_pointer_it)->calc_min_and_max_leaf_levels_and_print_if_they_belongs_to_segment
                    (
                        min_allowable_max_leaf_level,
                        max_allowable_max_leaf_level
                    );
 
                node_heights_set_.insert
                    (
                        (*child_pointer_it)->min_leaf_level() + 1
                    );
 
                node_heights_set_.insert
                    (
                        (*child_pointer_it)->max_leaf_level() + 1
                    );
            }//for
        }//if
 
        if  (
                    min_allowable_max_leaf_level    <=  min_leaf_level()
                &&  max_leaf_level()                <=  max_allowable_max_leaf_level
            )
        {
            std::cout   <<  "node_ID = "
                        <<  node_ID_
                        <<  '\t'
                        <<  T_levels_segment
                                (
                                    min_leaf_level(),
                                    max_leaf_level()
                                )
 
                        <<  std::endl;
        }//if
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    int  min_leaf_level()
    {
        return  node_heights_set_.empty()
                    ?   0
                    :   *node_heights_set_.begin();
    }
    //-----------------------------------------------------------------------------------
    int  max_leaf_level()
    {
        return  node_heights_set_.empty()
                    ?   0
                    :   *node_heights_set_.rbegin();
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    T_node*     tree    =   new     T_node(0);
    tree->to_node_with_ID_add_child_with_ID(0, 1);
    tree->to_node_with_ID_add_child_with_ID(0, 2);
    tree->to_node_with_ID_add_child_with_ID(0, 3);
 
    tree->to_node_with_ID_add_child_with_ID(1, 5);
    tree->to_node_with_ID_add_child_with_ID(1, 6);
 
    tree->to_node_with_ID_add_child_with_ID(2, 4);
 
    tree->to_node_with_ID_add_child_with_ID(3, 11);
 
    tree->to_node_with_ID_add_child_with_ID(4, 8);
    tree->to_node_with_ID_add_child_with_ID(4, 9);
 
    tree->to_node_with_ID_add_child_with_ID(6, 7);
 
    tree->to_node_with_ID_add_child_with_ID(9, 10);
 
    tree->to_node_with_ID_add_child_with_ID(11, 12);
 
    tree->to_node_with_ID_add_child_with_ID(12, 13);
    tree->to_node_with_ID_add_child_with_ID(12, 14);
 
    tree->to_node_with_ID_add_child_with_ID(14, 15);
 
    for(;;)
    {
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  "Введите желаемый диапазон уровней узлов поддерева от корня поддерева:"
                    <<  std::endl
                    <<  "min = ";
 
        int     min     =   0;
        std::cin    >>  min;
 
        std::cout   <<  "max = ";
        int     max     =   0;
        std::cin    >>  max;
 
        std::cout   <<  "Корни поддеревьев, листья которых находятся в этом диапазоне уровней от корня поддерева:"
                    <<  std::endl;
 
        tree->calc_min_and_max_leaf_levels_and_print_if_they_belongs_to_segment
            (
                min,
                max
            );
    }
}
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 734
24.03.2013, 08:42 #8
вам нужен массив степеней вершин. dfs-ом найдете расстояние от корня, и если оно удовлетворяет, и вершина является листом, - поддерево, содержащее ее, входит в ответ.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.03.2013, 08:42
Привет! Вот еще темы с ответами:

Найти все числа в заданном диапазоне, которые делятся на сумму своих цифр. - C++
Написать программу, содержащую не менее двух функций в разных файлах .c (.cpp), и три варианта определения функций: - нерекурсивная; ...

В заданном диапазоне найти все пары натуральных дружественных чисел, удовлетворяющих условию - C++
Два натуральных числа называются дружественными, если каждое из них равно сумме всех натуральных делителей другого (само число при этом не...

В заданном диапазоне найти все числа, которые делятся без остатка на a или на b - C++
Добрый вечер!Помогите решить лабу по программированию 1.Даны два числа aи b. Найдите среди чисел от 1 до 1000 все числа, которые...

Определить и вывести сумму элементов, значения которых находятся в диапазоне от А до В. Исправить ошибки - C++
Определить и вывести сумму элементов, значения которых находятся в диапазоне от А до В. int main() { int x,s=0,a,b; int k=0; ...


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

Или воспользуйтесь поиском по форуму:
8
Yandex
Объявления
24.03.2013, 08:42
Ответ Создать тему
Опции темы

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