Forums Back to the site
Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: Бинарные деревья
PostPosted: Fri Nov 11, 2011 10:55 am 
Offline
Beginner
Beginner
User avatar

Joined: Sun Feb 15, 2009 7:21 pm
Posts: 81
Location: Рыбинск
такая проблема. Задали задачу, не могу решить. На С++ билдере 6 написать программу. Разработать модель бинарного дерева, реализовать добавление/удаление узла, поиск(обход) по дереву и визуализация. Прошу помочь кто чем может.


Top
 Profile  
 
 Post subject: Re: Бинарные деревья
PostPosted: Fri Nov 11, 2011 2:22 pm 
Offline
Addicted
Addicted
User avatar

Joined: Tue Aug 31, 1993 10:00 pm
Posts: 201
Location: Maykop, Russia
Бинарные деревья — деревья, узлы которых могут иметь не более 2 потомков (называемых левым и правым поддеревьями). Их классический способ представления в памяти основывается на использовании указателей.

Для начала тебе нужно определиться со структурой узла дерева. То есть с тем, что ты намереваешься хранить в узле. Для простоты предположим, что ты будешь хранить в дереве целые числа типа int. Таким образом, тип узла дерева можно задать таким образом:

Code:
typedef struct {
TreeNode *left; // указатель на левое поддерево
TreeNode *right; // указатель на правое поддерево
int value; // непосредственно данные
} TreeNode;


Каждый узел дерева представляет собой структуру из 3 элементов:
— данные, хранимые в узле
— указатель на левое поддерево
— указатель на правое поддерево

Указатели на поддеревья — это указатели на другие экземпляры структур такого вида. В случае, если у узла нет поддерева, значение соответствующего указателя делается равным 0. Таким образом, простейшее бинарное дерево — пустое дерево — строится таким образом:

Code:
TreeNode *root = 0;


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

Code:
// Объект в стеке
TreeNode root;
root.left = 0;
root.right = 0;
root.value = 42;

// Объект в динамической памяти
TreeNode *root = (TreeNode *) malloc(sizeof(TreeNode));
root->left = 0;
root->right = 0;
root->value = 42;


Нет принципиальной разницы где хранить элементы, правило лишь одно: память в стеке уже выделена твоему приложению, за счёт этого она работает быстрее, но её относительно мало, динамической памяти же у тебя в распоряжении сколь угодно много, но она работает чуть медленнее (но не настолько, чтобы в примитивных задачах была заметна разница).

Добавление элемента в дерево осуществляется по следующему алгоритму: если корень пуст, создаётся новый экземпляр TreeNode и элемент помещается в него; левые и правые поддеревья помечаются пустыми. Если же в корне есть элемент R, то значение R.value сравнивается со значением впиливаемого элемента x и, если x меньше, чем R.value, то аналогичным образом рассматривается левое поддерево R.left. Если оно пусто, элемент впиливается в это место (с пустыми поддеревьями), если не пусто, снова происходит сравнение добавляемого элемента с данным, для того, чтобы определить, влево или вправо двигаться. На каком-то шаге может получиться так, что элемент уже присутствует в дереве. Тут уже всё зависит от постановки твоей задачи — можно ничего не делать, а можно, например, ввести в структуру TreeNode ещё одно поле — счётчик, показывающий, сколько элементов с данным значением хранится в дереве.

Попробуй реализовать для начала это, а там дальше видно будет… :roll:

С визуализацией, сразу говорю, не помогу, ибо пишу на Qt под Linux, под Windows на этомвашем Builder не представляю как под GUI программировать.

_________________
Машины не ставить! Работает экзегутор.


Top
 Profile  
 
 Post subject: Re: Бинарные деревья
PostPosted: Fri Nov 11, 2011 6:31 pm 
Offline
Beginner
Beginner
User avatar

Joined: Sun Feb 15, 2009 7:21 pm
Posts: 81
Location: Рыбинск
Если честно, из того, что написано, понятно довольно мало.


Top
 Profile  
 
 Post subject: Re: Бинарные деревья
PostPosted: Fri Nov 11, 2011 11:51 pm 
Offline
Addicted
Addicted
User avatar

Joined: Tue Aug 31, 1993 10:00 pm
Posts: 201
Location: Maykop, Russia
Fisher92 wrote:
Если честно, из того, что написано, понятно довольно мало.

Увы, я не могу помочь, пока не узнаю, что конкретно не понятно. Задавай конструктивные вопросы, на которые можно дать ответ — привести код, нарисовать иллюстрацию, расказать теорию…

_________________
Машины не ставить! Работает экзегутор.


Top
 Profile  
 
 Post subject: Re: Бинарные деревья
PostPosted: Sat Nov 12, 2011 6:55 pm 
Offline
Beginner
Beginner
User avatar

Joined: Sun Feb 15, 2009 7:21 pm
Posts: 81
Location: Рыбинск
мне бы увидеть как уже примерно программа должна выглядеть.


Top
 Profile  
 
 Post subject: Re: Бинарные деревья
PostPosted: Sun Dec 18, 2011 11:13 pm 
Offline
Beginner
Beginner
User avatar

Joined: Sun Feb 15, 2009 7:21 pm
Posts: 81
Location: Рыбинск
Вот всё думал, думал, не смог придумать. Как объединить эти куски кода, что ты мне дал, чтобы что-нибудь внятное получилось.


Top
 Profile  
 
 Post subject: Re: Бинарные деревья
PostPosted: Sun Dec 18, 2011 11:14 pm 
Offline
Beginner
Beginner
User avatar

Joined: Sun Feb 15, 2009 7:21 pm
Posts: 81
Location: Рыбинск
И ещё. Как поиск можно реализовать?


Top
 Profile  
 
 Post subject: Re: Бинарные деревья
PostPosted: Mon Dec 26, 2011 6:24 pm 
Offline
Addicted
Addicted
User avatar

Joined: Tue Aug 31, 1993 10:00 pm
Posts: 201
Location: Maykop, Russia
Fisher92 wrote:
И ещё. Как поиск можно реализовать?

Бинарное дерево само по себе чаще всего используется как инструмент для поиска, то есть в узлах ты хранишь ключи и какие-либо данные, и доступ к данным по ключу при использовании дерева будет быстрее, чем при использовании сканирования множества ключей.
http://codingrus.ru/readarticle.php?article_id=2152

Таким образом, обращение к узлу дерева по содержащемуся в нём значению ключа — это и есть поиск.

_________________
Машины не ставить! Работает экзегутор.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron