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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
wtfdotka
0 / 0 / 0
Регистрация: 25.12.2011
Сообщений: 12
22.03.2013, 15:58     Работа с деревьями (Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева) #1
Есть задача:
Дано N-дерево. Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева.
Дайте советы по алгоритму решения, допустим прохожу дерево, нахожу лист, который в заданном диапозоне, как дальше вывести все поддеревья с этим листом, имея, например, сейчас только указатель на этот лист?Можно ли все это сделать за один обход дерева? Или как сократить количество обходов? Помогите советом

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

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

Вы сначала чётко сформулируйте задачу, а уж потом спрашивайте советов. Мы не телепаты.
wtfdotka
0 / 0 / 0
Регистрация: 25.12.2011
Сообщений: 12
22.03.2013, 16:38  [ТС]     Работа с деревьями (Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева) #5
Задача четко сформулирована в первом посте, я так же как и вы пытаюсь понять ее условие. Если смотреть во вашему рисунку, но алгоритм примерно такой? проходим дерево до уровня Нижняя граница -1 и проверяем условие не являются ли какой из сыновей узла листом?Только еще вопрос, как обознать поддерево с си? Нужно найти узел, сын которого лист, но тогда будут другие ветви или нужно найти ветвь, как вы указали на рисунке, то я не знаю как это обозначить, указатель на узел и указатель на сына-листа?
fjay69
 Аватар для 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, содержащий этот лист.
Алсо, чтобы задача имела практическое значение, нужны методы, с помощью которых можно перемещаться по деревьям и создавать/удалять/изменять деревья/листья
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
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
            );
    }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.03.2013, 08:42     Работа с деревьями (Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева)
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
24.03.2013, 08:42     Работа с деревьями (Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева) #8
вам нужен массив степеней вершин. dfs-ом найдете расстояние от корня, и если оно удовлетворяет, и вершина является листом, - поддерево, содержащее ее, входит в ответ.
Yandex
Объявления
24.03.2013, 08:42     Работа с деревьями (Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева)
Ответ Создать тему
Опции темы

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