Форум программистов, компьютерный форум CyberForum.ru

Построение бинарного дерева - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 53, средняя оценка - 4.62
dikdiv
0 / 0 / 0
Регистрация: 17.12.2009
Сообщений: 4
20.12.2009, 23:02     Построение бинарного дерева #1
Доброй ночи! Пятые сутки не могу разобрать реализацию алгоритма на С++ Console Wizzard! Что такое бинарное дерево я знаю, даже разобрал ДДП! Вообще по задаче, надо написать англо-русский словарь, т.е. ключами у меня будут английские слова, которые будут браться из .txt файла. Не понимаю именно где хранятся эти ключи (надо их записывать в ОЗУ из .txt файла, при запуске программы), в символьном массиве? мне подсказали что надо использовать указатели, но я не очень дружу с ними... помогите разобраться с тем, как и где хранить ключи в дереве???

p.s. вообще, мне надо понять как строить двоичное дерево, т.е. не обязательно на примере словаря.

Добавлено через 2 минуты
вообще, мне подсказывали, что надо сначала создать пустое дерево, а потом туда поочередно добавлять ключи, ну тогда придется создавать очень много переменных...???
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
20.12.2009, 23:09     Построение бинарного дерева #2
правельно подсказали.
открываешь файл. создаешь пустое дерево. заполняешь дерево материалом из файла.
каждый элемент дерева должен иметь два поля "русское слово" и "английское слово".
dikdiv
0 / 0 / 0
Регистрация: 17.12.2009
Сообщений: 4
20.12.2009, 23:33  [ТС]     Построение бинарного дерева #3
ага!)) допустим в переменной buf лажат эти оба слова, но мне надо только английское, допустим я реализовал это и новое английское слово лежит в перем. buf1, теперь надо добавить это слово в дерево, т.е. первое слово из файла у меня будет корнем дерева (kor), смотрю след. слово, сравниваю его функцией strcmp и присваиваю левому или правому сыну, вот тут мне не понятно??? надо создать еще одну переменную, а потом для другого слова еще одну переменную, и еще и так сотни переменных для каждого слова, а потом вообще путаница получается...(((????

Добавлено через 17 минут
ну помогите плиииизз!!!
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
21.12.2009, 07:46     Построение бинарного дерева #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
да. путаницы не будет если сделать правельный обход дерева
что то вроде этого:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
struct node{
       string word1;//английское слово - ключ для поиска.
       string word2;//русское слово.
       node* left;//левый сын.
       node* right;//правый сын.
       node (string S1,string S2)//ГЄГ®Г*ñòðóêòîð
       {
            word1=S1;
            word2=S2;
            left=0;
            right=0;
       }
       void add(string S1,string S2)//äîáГ*âëåГ*ГЁГҐ ýëåìåГ*ГІГ*
       {
            int i=0;
            while (S1[i]==word1[i])i++;//ГІГіГІ ГЁГ№ГЁГ¬ ïåðâóþ Г*ГҐ ñîâïГ*Г¤Г*ГѕГ№ГіГѕ ГЎГіГЄГўГі äâóõ ñëîâ.
            //åñëè Гі ГІГҐГЄГіГ№ГҐГЈГ® óçëГ* ГҐГ±ГІГј ГўГҐГІГўГЁ. ГІГ® Г*Г*äî äîáГ*ГўГЁГІГј Гў ГЅГІГЁ ГўГҐГІГўГЁ.
            if ((S1[i]>word1[i])&&left) left->add(S1,S2);
            if ((S1[i]<word1[i])&&right) right->add(S1,S2);
 
            //åñëè Гі ГІГҐГЄГіГ№ГҐГЈГ® óçëГ* Г*ГҐГІГі ГўГҐГІГўГҐГ© Г*Г*äî áîáГ*ГўГЁГІГј ГЄ ГҐГЈГ® left èëè right.
            if ((S1[i]>word1[i])&& !left) {new p=node(S1,S2); left=&p;}
            if ((S1[i]<word1[i])&& !right){new p=node(S1,S2); right=&p;}
        }
        void print(int n)//âûâîä Г*Г* ГЅГЄГ°Г*Г*
        {
             if (left)left->print(n+1);
             for (int i=0;i<n;i++)cout << "    " ;cout <<word1 <<"="<<word2<<endl;
             if (right)light->print(n+1);
        }
        string search(string s) //ïîèñê ñëîâГ* ГЇГ® êëþ÷ó
        {
               if (s==word1)return word2; //êëþ÷ ñîâïГ*Г«.
               int i=0;
               while (S1[i]==word1[i])i++;//ГІГіГІ ГЁГ№ГЁГ¬ ïåðâóþ Г*ГҐ ñîâïГ*Г¤Г*ГѕГ№ГіГѕ ГЎГіГЄГўГі äâóõ ñëîâ.
               //Г±ГЇГіГ±ГЄГ*åìÿ âëåâî èëè ГўГЇГ°Г*ГўГ®.
               if ((S1[i]>word1[i])&&left) return left->search(s);
               if ((S1[i]<word1[i])&&right) return right->search(s);
        }
};
 
struct tree{
       node *link;
       tree(){link=0;}
       void add(string S1,string S2)
       {
            if (link) link->add(S1,S2);
            else {new p=node(S1,S2);link=&p;}
       }
       void print(){if (link)link->print(1);else cout << "Tree is empty\n";}
       string search(string s){if (link) return link->search(s);else cout << "Tree is empty\n";return "error";}
};
 
int main()
{
    tree T;//создали пустое дерево.
    T.add("Hello","Privet");
    T.add("Goodby","Poka");
    T.add("Dog","Sobaka");
    T.add("Pain","C++");
    T.add("Car","Avtomobil");
    T.print();//вывели содержимое дерева на экран
    
    string s=T.search("Dog");//совершили поиск по ключу
    cout << s<<endl;
}
на экран выведется:
Sobaka

не забудь добавить функции удаляющие дерево, и еще какие нибудь, что бы покошернее было (напимер заполнение дерева из файла).
Yandex
Объявления
21.12.2009, 07:46     Построение бинарного дерева
Ответ Создать тему
Опции темы

Текущее время: 10:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru