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

STL пойдет?

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

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

STL пойдет?

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

Это сообщение отредактировал(а) Дрон - 31.5.2005, 23:35

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

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

Берём первую фамилию. Записываем в корень дерва.
Берём следующую. Сравниваем с первой. Если меньше, то записываем в левую ветвь, если больше, то в правую (меньше или больше это можно определить функцией 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)       {               // два одинаковых имени -- по идее это ошибка       } }

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

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

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

Знаю знаю!

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


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

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



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

Цитата

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

Нет.

Цитата

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

Едва ли.

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

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

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

Эффективнее - конечно, а вот насчет проще - вряд ли
К тому же, в задании явно указано бинарное дерево.

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

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

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

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

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

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

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

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

1
2