Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > n-мерные деревья

Автор: toxx 16.3.2010, 23:10

Задача состоит в удалении поддеревьев с определенным числом листьев( 3,4 это уже не бинарное дерево).Если я правильно понял это n-мерное дерево или граф,
пока точно не понял, помогите разобраться.
Подскажите пожалуйста литературу и ссылки на реализацию n- мерных деревьев, в интернете/книгах информация только о бинарных деревьях.

Автор: Earnest 17.3.2010, 08:48

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

Автор: toxx 17.3.2010, 11:12

Цитата(Earnest @ 17.3.2010, 08:48)

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

Код


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

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

Автор: Artemon 17.3.2010, 12:58

Например так:

Код


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

Автор: Earnest 17.3.2010, 13:02

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

Автор: toxx 17.3.2010, 16:52

Earnest,Artemon

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

Автор: ИванМ 17.3.2010, 20:00

Цитата(toxx @ 17.3.2010, 16:52

)

как можно добавлять вершины/листья если не фиксированное число листьев(вершин).

Код


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

Автор: Earnest 18.3.2010, 09:36

Цитата(toxx @ 17.3.2010, 17:52

)

Отсутствие книг тоже пугает, без них сложновато.

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

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

Автор: cmygeHm 5.8.2010, 08:50

Ребят, как вот такую вот такое вот дерево в XML выгрузить? Как пройтись по всем листьям дерева?

Автор: kemiisto 5.8.2010, 09:34

[offtopic]

Цитата(Earnest @ 18.3.2010, 10:36

)

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

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

[/offtopic]

Автор: toxx 5.8.2010, 09:50

обходить както так

Код


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;
    }
}

Автор: Earnest 5.8.2010, 09:51

kemiisto, почему только С\С++? По моему, к любому программированию относится. Даже если что-то сделаешь неправильно\неудачно, ничего, кроме времени, не потратишь и не испортишь безвозвратно, и любую ошибку можно устранить гораздо дешевле чем в реале. smile

cmygeHm, как обходить дерево, читай в книгах. В общих словах, существуют 2 разных способа - в ширину и в глубину. А куда этот обход засунуть - в XML или еще куда - дело десятое.
И следующий раз не пиши в чужих темах, создай свою.

Автор: cmygeHm 5.8.2010, 10:11

Цитата(Earnest @ 5.8.2010, 09:51

)

И следующий раз не пиши в чужих темах, создай свою.

Ради такого я бы не стал тему создавать, я бы сам поднатужился smile

Извините.