Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> n-мерные деревья 
V
    Опции темы
toxx
Дата 16.3.2010, 23:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13
Задача состоит в удалении поддеревьев с определенным числом листьев( 3,4 это уже не бинарное дерево).Если я правильно понял это n-мерное дерево или граф, 
пока точно не понял, помогите разобраться.
Подскажите пожалуйста литературу и ссылки на реализацию n- мерных деревьев, в интернете/книгах информация только о бинарных деревьях.
PM MAIL   Вверх
Earnest
Дата 17.3.2010, 08:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183
Да какая разница? В n-мерном дереве не 2 потомка у элемента, а больше, вот и все. С точки зрения хранения, удаления и прочего - нет большой разницы. Просто бинарные деревья имеют некие специальные свойства и применения, вот о них много и пишут. Что касается графов, то да, дерево - частный случай графа. Но устройство графа сложнее, так что если тебе нужно именно дерево (т.е. иерархическая структура), лучше дерево и строй.



--------------------
...
PM   Вверх
toxx
Дата 17.3.2010, 11:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13
Цитата(Earnest @ 17.3.2010,  08:48)
Да какая разница? В n-мерном дереве не 2 потомка у элемента, а больше, вот и все. С точки зрения хранения, удаления и прочего - нет большой разницы. Просто бинарные деревья имеют некие специальные свойства и применения, вот о них много и пишут. Что касается графов, то да, дерево - частный случай графа. Но устройство графа сложнее, так что если тебе нужно именно дерево (т.е. иерархическая структура), лучше дерево и строй.

Да, как я нашел разницы особой нет. Но мне интересно
1.Какая структура будет у н-мерного дерева, если у бинарного такая
Код

struct Node
{
    int d;
    Node *left;
    Node *right;
};

2.Какое условие сделать при добавлении элемента?
У бинарного всё понятно больше правое поддерево, меньше левое.

Это сообщение отредактировал(а) toxx - 17.3.2010, 11:12
PM MAIL   Вверх
Artemon
Дата 17.3.2010, 12:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


а ты мне нравишься
***


Профиль
Группа: Завсегдатай
Сообщений: 1771
Регистрация: 24.2.2004
Где: Челябинск

Репутация: 1
Всего: 20
Например так:

Код

struct Node
{
    int d;
    std::vector<Node *> Nodes;
};



--------------------
Контроль топлива на топливозаправщиках, мониторинг автотранспорта, расчет зарплаты водителей www.rscat.ru
PM MAIL   Вверх
Earnest
Дата 17.3.2010, 13:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183
1. Например, массив указателей на детей - если число детей строго ограничено и невелико. Или список. Или вектор.
2. Больше-меньше - это не просто двоичное дерево, а дерево поиска. А просто двоичное - без разницы кого куда. Соответственно, для произвольного дерева просто добавляем элемент в список детей. Для какой-то конкретной задачи при добавлении элемента  может происходить какой-то анализ и спуск элемента по ветвям. Но в общем случае - все тупо. 


--------------------
...
PM   Вверх
toxx
Дата 17.3.2010, 16:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13
Earnest,Artemon

До конца я не понимаю как можно добавлять вершины/листья если не фиксированное число листьев(вершин).
Наверно нужно попробовать сделать.
Спасибо, что маленько прояснили(хоть структура какая должна быть ясно).А литература кроме Вирта и Кнута есть какая-нибудь?
В Вирте написано в основном про двоичные,бинарные деревья.Отсутствие книг тоже пугает, без них сложновато.


Это сообщение отредактировал(а) toxx - 17.3.2010, 16:53
PM MAIL   Вверх
ИванМ
Дата 17.3.2010, 20:00 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1260
Регистрация: 19.6.2006
Где: СПб

Репутация: 1
Всего: 23
Цитата(toxx @  17.3.2010,  16:52 Найти цитируемый пост)
как можно добавлять вершины/листья если не фиксированное число листьев(вершин).

Код

struct Node
{
    int d;
    std::vector<Node *> Nodes;
    //добавление новой вершины
    void AddNode(Node* node)
    {
        Nodes.push_back(node);
    }
};




Это сообщение отредактировал(а) ИванМ - 17.3.2010, 20:00
PM MAIL   Вверх
Earnest
Дата 18.3.2010, 09:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183
Цитата(toxx @  17.3.2010,  17:52 Найти цитируемый пост)
Отсутствие книг тоже пугает, без них сложновато.

Чего бояться-то, не дом строишь, на голову не упадет. Компьютер тем и хорош, что все стерпит. Книги хорошо, но голову тоже включать надо. Дерево - структура простая, тебе все написали, собственно. Дальше - твори.

Добавлено через 3 минуты и 30 секунд
Но хорошую книгу все же назову: Роберт Седжвик, Фундаментальные алгоритмы на С, части 1-4 посвящены структурам данных и алгоритмам, часть 5 - графы. Про деревья общего вида там немного, но достаточно, чтобы разобраться.


--------------------
...
PM   Вверх
cmygeHm
Дата 5.8.2010, 08:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 3.12.2008

Репутация: -1
Всего: -2
Ребят, как вот такую вот такое вот дерево в XML выгрузить? Как пройтись по всем листьям дерева?
PM MAIL   Вверх
kemiisto
Дата 5.8.2010, 09:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дикий Кот. =^.^=
****
Награды: 1



Профиль
Группа: Участник Клуба
Сообщений: 3292
Регистрация: 29.7.2007

Репутация: 2
Всего: 160
[offtopic]
Цитата(Earnest @  18.3.2010,  10:36 Найти цитируемый пост)
Чего бояться-то, не дом строишь, на голову не упадет. Компьютер тем и хорош, что все стерпит.

Это в рамочку и на стенку. Философия С/С++. smile 
[/offtopic]


--------------------
XMPP-канал.

Unit testing isn't enough. You need static typing.

Пей, кури, пиши на си! smile
PM MAIL WWW GTalk Jabber   Вверх
toxx
Дата 5.8.2010, 09:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13
обходить както так
Код

void Tree::print(Tree* root,size_t level)
{
    if(root)
    {
        for(size_t i=0;i<root->Trees.size();i++)
            print(root->Trees[i],level+1);
        for(size_t i=0;i<level;i++)
            cout<<"   ";
        cout<<root->d<<endl;
    }
}



Это сообщение отредактировал(а) toxx - 5.8.2010, 09:50
PM MAIL   Вверх
Earnest
Дата 5.8.2010, 09:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183
kemiisto, почему только С\С++? По моему, к любому программированию относится. Даже если что-то сделаешь неправильно\неудачно, ничего, кроме времени, не потратишь и не испортишь безвозвратно, и любую ошибку можно устранить гораздо дешевле чем в реале. smile 
cmygeHm, как обходить дерево, читай в книгах. В общих словах, существуют 2 разных способа - в ширину и в глубину. А куда этот обход засунуть - в XML или еще куда - дело десятое. 
И следующий раз не пиши в чужих темах, создай свою.


--------------------
...
PM   Вверх
cmygeHm
Дата 5.8.2010, 10:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 3.12.2008

Репутация: -1
Всего: -2
Цитата(Earnest @  5.8.2010,  09:51 Найти цитируемый пост)
И следующий раз не пиши в чужих темах, создай свою.


Ради такого я бы не стал тему создавать, я бы сам поднатужился smile Извините.
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0629 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.