Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
4 / 4 / 2
Регистрация: 24.05.2013
Сообщений: 300
1

Как правильно организовать дерево ?

27.06.2017, 12:01. Просмотров 605. Ответов 7
Метки нет (Все метки)

Есть класс дерева (упрощенный вариант)
C++
1
2
3
4
5
6
class Tree {
public:
Tree * parent;
int data;
vector<Tree> childs;
}
Предположим я хочу создать 3х уровненое дерево.
C++
1
2
3
    *         // 0 level
 *     *     // 1 level
* *   * *    // 2 level
Создаю дерево поуровнево.
Создав второй уровень, я добавил все деревья второго уровня в вектор. Все родители второго уровня указывают на корень.
C++
1
vector<Tree> level2;
Ок. Вектор есть. Добавим третий уровень. После добавление третьего уровня, родители обьектов в векторе теперь указывают на ! обьект нового уровня !, то есть на третий уровень. Он указывает на одного из своего ребенка.
C++
1
2
3
4
// выходит
level2[i].parent -> (level3)
level2[i].parent.parent -> (получаю level[i] собственной персоной)
level2[i].parent.parent.parent -> (level3)
Выходит что до корня не добратся Бесконечный цикл...
Что не так, как правилно выполнить такую задачу. Необходимо в векторе хранить все деревья определенного уровня. А после добавления нового, от хранимых деревьев пройтись до корня (подняться вверх).
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.06.2017, 12:01
Ответы с готовыми решениями:

Как правильно организовать ветвление в программе? (if / else if)
Доброгл времени суток. Есть вопрос - почему если я ввожу нужный мне параметр мне всплывает на экран...

Как правильно организовать большой проект?
В будущем хочу участвовать в разработке игр - начал изучать С++, вопрос тут такой, как правильно...

Как правильно организовать многофайловый проект?
Добрый вечер дорогой форум. Сразу скажу я новичек. Пишу курсовик, сроки, как всегда поджимают...

Как правильно организовать код большого проекта на C++?
Все мы рано или поздно переходим тот рубеж, когда писать хелловорлды становится скучно и хочется...

7
Форумчанин
Эксперт CЭксперт С++
8161 / 5009 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
27.06.2017, 12:05 2
Без перевода курсора выводить дерево вертикально достаточно сложно (и нерационально). Обычно делают рекурсивный вывод горизонтально.
0
92 / 68 / 22
Регистрация: 17.10.2011
Сообщений: 235
27.06.2017, 12:34 3
Цитата Сообщение от Evgen8 Посмотреть сообщение
Необходимо в векторе хранить все деревья определенного уровня. А после добавления нового, от хранимых деревьев пройтись до корня (подняться вверх).
можно пользовать reference_wrapper
C++
1
2
3
4
5
6
7
8
9
10
struct Node {
    Node(int _data):parent(0),data(_data){};
    Node* parent;
    int data;
    vector<reference_wrapper<Node>> childs;
};
class Tree{
public:
    Tree(int data):nodes(vector<vector<Node>>(1,vector<Node>(1,Node(data)))){};
    vector<vector<Node>> nodes;
0
4 / 4 / 2
Регистрация: 24.05.2013
Сообщений: 300
27.06.2017, 20:17  [ТС] 4
Цитата Сообщение от MrGluck Посмотреть сообщение
Без перевода курсора выводить дерево вертикально достаточно сложно (и нерационально). Обычно делают рекурсивный вывод горизонтально.
вроде как раз легко пройтись снизу-вверх рекурсивно через родителя. (мб, я вас не понял)

vndtta, честно не сильно понял ваш исходник.

Я так понимаю вектор хранит копии обьектов , но не ссылки ?
0
Комп_Оратор)
Эксперт по математике/физике
8614 / 4332 / 584
Регистрация: 04.12.2011
Сообщений: 12,942
Записей в блоге: 14
27.06.2017, 22:13 5
Evgen8, я бы использовал список. Потому, что итераторы вектора теряют валидность при добавлении/удалении и в следствии, указатель на родителя может показывать в никуда. Указатель на элемент списка более надёжен, может быть. Хотя я бы пошёл дальше и заменил его итератором элемента списка. Тогда более однородно получится.
0
92 / 68 / 22
Регистрация: 17.10.2011
Сообщений: 235
28.06.2017, 08:16 6
Цитата Сообщение от Evgen8 Посмотреть сообщение
Я так понимаю вектор хранит копии обьектов , но не ссылки ?
вектор хранит все узлы дерева, например nodes[0][0] - корень
nodes[1] - вектор узлов первого уровня и т.д.
а в самих узлах хранятся только ссылки childs
1
4 / 4 / 2
Регистрация: 24.05.2013
Сообщений: 300
28.06.2017, 15:36  [ТС] 7
Ссылки / указатели сбиваются после добавления нового ребенка. Это даже логично... Обьект имеет адрес. Меняется обьект - > он обновляется -> обновляется его адрес (почти всегда адрес изменяется...). Старые указатели/ссылки показывают на что-то левое. Правильно это понимаю ?
Изначально я собирал вектор обьектов, вроде в нем хранятся копии. Так как добавления нового ребенка к дереву, не убивает те деревья, которые в векторе. Но опять же, указатели на родителя в них сбиваются, показывая теперь на что-то левое.
vndtta, вы предложили хранить прямо в дереве данный вектор. Этот вектор часть обьекта, при обновлении обьекта - > обновится и вектор. Ок. А что по поводу вариантов, не изменяющих сам класс Tree ? Это вообще возможно сделать ?

Добавлено через 4 минуты
Различия в них для себя не нашел...Оба сбиваются.
C++
1
2
vector<reference_wrapper<Tree>> trees0;
vector<Tree *> trees0;
Добавлено через 16 минут
C++
1
2
3
4
5
6
7
8
Tree myTree;
 
Tree * pointer = &myTree;
Tree & reference = myTree;
 
myTree.AddChild(...);
myTree.AddChild(...);
myTree.AddChild(...);
Указатель будет левым, а ссылка нет. Так вроде должно быть... Но на практике оба правильно ссылаются. Что я не так понимаю ?
0
Комп_Оратор)
Эксперт по математике/физике
8614 / 4332 / 584
Регистрация: 04.12.2011
Сообщений: 12,942
Записей в блоге: 14
28.06.2017, 17:39 8
-У Вас в ушах бананы.
-A-a?! Что-о?!
-У Ва-а-с!!! - в уша-ах! - ба-анаа-а-аны-ы!!!.
-Говорите громче, -у меня в ушах бананы.

Цитата Сообщение от Evgen8 Посмотреть сообщение
Ссылки / указатели сбиваются после добавления нового ребенка.
Цитата Сообщение от IGPIGP Посмотреть сообщение
я бы использовал список
Попробуйте std::list
Вообще, рекурсивные типы, это достаточно сложная концепция. Если возникают вопросы вроде:
Цитата Сообщение от Evgen8 Посмотреть сообщение
указатели сбиваются после добавления нового ребенка. Это даже логично...
Может заняться более простыми задачами?
Можно использовать список указателей, кстати. Но придётся заниматься памятью, вручную. Зато получите полиморфную совместимость. А если использовать список итераторов (тут о дин. полиморфизме, - забыть , зато с памятью не нужно возиться ) на объекты списка, то можно создать класс в котором два вида списка. Один:
list<T> -общее хранилище ,
- другой:
list<list<T>::const_iterator> - список дочерних элементов каждого нода.
То есть довольно интеллектуально может выглядеть, если связь выразить не формально, а функционально.
Посмотрите в архиве вот тут, если интересно:
https://www.cyberforum.ru/blog... g4772.html

Не по теме:

там зависимости тоже достаточно формальны. Нет блоков вычисления и анализа предикат... Но пока так. Для поиска, общего назначения простой предикат - более удобен. Не связывает пользователя своими правилами. Впрочем, это уже не по теме.:)

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.06.2017, 17:39

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Как правильно организовать файловый ввод/вывод?
setlocale(LC_ALL,&quot;russian&quot;); double x; ifstream fin; fin.open(&quot;input.txt&quot;); ...

Как правильно организовать удаление объекта по указателю?
Конечно тема избитая, и я находил много решений, но проверить удаляються ли объекты не могу. Есть...

Как правильно организовать дописывание данных в звуковой файл
У меня есть TCP сервер написанный на Qt. Сервер у меня создается как отдельный класс Server в...

Как правильно организовать заголовочный файл со своими функциями?
Есть файл в котором я храню функции, которые часто использую(среди них есть и шаблонные)....

Конструктор дерева (не бинарного). Или как вообще правильно строить дерево?
Хочу разобраться с деревьями, да что только не читал, не пересматривал - не могу разобраться. Для...

Нюансы ввода/вывода: как правильно организовать ввод строки с пробелами?
Доброе время суток. Такой вопрос: у меня есть структура, содержащая ФИО, адрес, телефон, возраст....


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

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

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