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

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

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

Автор: Гость_Fred 31.5.2005, 20:33

Ребята помогите кто-нибудь реализовать двоичное дерево
вот само условие
"На междугородной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована как двоичное дерево.
Составить программу, которая:
• обеспечивает начальное формирование картотеки в виде двоичного дерева;
• производит вывод всей картотеки;
• вводит номер телефона и время разговора;
• выводит извещение на оплату телефонного разговора.
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе."
Горю выручайте ... smile

Автор: bel_nikita 31.5.2005, 23:24

STL пойдет?

Автор: Дрон 31.5.2005, 23:33

Во первых из условия не понятно, что именно должно служить основой формирования дерева. Фамилии абонентов или номера телефонов? Дальше непонятно откуда берётся информация о времени разговора?

Цитата(bel_nikita @ 1.6.2005, 00:24)

STL пойдет?

А смысл? Взять и всё запихнуть в map это очень соблазнительно, но у него это лаба по программированию smile

Я бы её рублей в 500 оценил smile

Автор: Guest 1.6.2005, 23:35

А как вообще строится двоичное дерево?
Или можно это программу реализовать в виде списков (односвязанных,двухсвязанных)?
Мне нужна просто сама реализация а уж до остального как нибудь сам допетрюсь, с динамикой у меня туган ....

Автор: Дрон 2.6.2005, 00:31

Ну если, например, строить дерево по фамилиям, то принцип такой:

Берём первую фамилию. Записываем в корень дерва.
Берём следующую. Сравниваем с первой. Если меньше, то записываем в левую ветвь, если больше, то в правую (меньше или больше это можно определить функцией strcmp).
Дальше сравниваем третью фамилию с корнем. Пусть она тоже меньше, как и вторая. Тогда переходим в левую ветвь и сравниваем со второй. Если она меньше второй, то пишем в левую ветвь второй, иначе в правую второй.
И т.д.

Примерно так:

Код


class TreeNode
{
     char *name;
     TreeNode *left,*right;
public:
     TreeNode(const char* str) { left=right=NULL; name=strcpy(str); }
     void Add(const char* str);
};

void TreeNode::Add(const char* str)
{
      int p = strcmp(str,name);
      if(p>0)
      {
            if(right == NULL) 
                  right = new TreeNode(str);
            else
                  right->Add(str);
      }
      else if (p<0)
      {
            if(left == NULL) 
                  left = new TreeNode(str);
            else
                  left->Add(str);
      }
      else if (p == 0)
      {
              // два одинаковых имени -- по идее это ошибка
      }
}

Обязательно надо написать деструктор, чтобы освободить память от строк и удалить дерево.
Да и вообще код не проверял smile

Автор: Fredy 2.6.2005, 00:33

Спасибо!! Дрон попробую разобраться!!! Если что обращусь за помощью!!

Автор: Знак 2.6.2005, 10:19

Ха так этож двоичное дерево Хофмана..!

Знаю знаю!

тебе надо сжать информацию? для тичера?

Вот почитайка

http://algolist.manual.ru/compress/standard/huffman.php

smile

Крутая тема и тичер будет доволен!!

Автор: Void 2.6.2005, 19:12

Цитата

Ха так этож двоичное дерево Хофмана..!

Нет.

Цитата

тичер будет доволен!!

Едва ли.

Автор: ___Yuri 2.6.2005, 19:57

Дрон, а может выть проще и эффективнее было сделать AVL дерево?
Или что нубудь типа Б - дерева - если записей уж очень много(как по идее и должно быть)?

Автор: Void 3.6.2005, 05:07

Цитата(___Yuri @ 2.6.2005, 21:57)

может выть проще и эффективнее было сделать AVL дерево?

Эффективнее - конечно, а вот насчет проще - вряд ли smile

К тому же, в задании явно указано бинарное дерево.

Автор: Знак 3.6.2005, 12:08

чем различны Бинарное и двоичное деревА smile

Автор: borisvolfson 3.6.2005, 17:16

Бинарное и двоичное дерево - это одна и таже структура данных.
Что касается, AVL-деревьев - это тоже бинарные деревья со своийствами сбалансированности, в них можно осуществлять быстрый поиск и вставку.

Автор: Void 3.6.2005, 19:22

Цитата(borisvolfson @ 3.6.2005, 19:16)

Что касается, AVL-деревьев - это тоже бинарные деревья со своийствами сбалансированности, в них можно осуществлять быстрый поиск и вставку.

Я знаю. Вторая фраза относилась уже к B-деревьям - недоквотил.

Автор: Знак 4.6.2005, 08:51

А кто моге ссылку на описание подкинуть ?

по AVL - деревьям... smile

тока точную а то я задиплюсь в инете smile

Автор: Alastis 4.6.2005, 12:48

http://www.idknet.com/isp/development/bin_trees/avl.htm
http://www.junik.lv/~georg/programming/sa/avl.htm