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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
MrGluck
Модератор
Эксперт CЭксперт С++
7158 / 4324 / 630
Регистрация: 29.11.2010
Сообщений: 11,745
#1

бинарные деревья - C++

22.10.2011, 00:53. Просмотров 1335. Ответов 5
Метки нет (Все метки)

Вот у меня есть программа, которая создает бинарное дерево из массива целых чисел.
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <conio.h>
using namespace std;
 
struct  bin_tree
{
   int value;
   bin_tree *left, *right;
}*pHead = NULL; // ГіГЄГ*Г§Г*òåëü Г*Г* âåðøèГ*Гі Г°Г*ГўГҐГ* Г*óëþ
 
// äîáГ*âëåГ*ГЁГҐ óçëГ* äåðåâГ*
void add_node(bin_tree* tree, int value); 
// ïðîâåðêГ* Г*Г* "ïóñòîòó" äåðåâГ*, åñëè ГіГЄГ*Г§Г*òåëü Г*Г* âåðøèГ*Гі Г°Г*ГўГҐГ* Г*óëþ, ñîçäГ*ГҐГІ óçåë
void add_bin_tree(int value);
//ÐåêóðñèâГ*Г® Г°Г*Г±ГЇГҐГ·Г*òûâГ*ГҐГ¬ ГЅГІГ® äåðåâî îò ìåГ*ГјГёГҐГЈГ® ýëåìåГ*ГІГ* ГЄ áîëüøåìó
void print(bin_tree* tree, int level);
 
int main()
{
    int mass[] = {10, 12, 19, 92, 1, 9, 20, 10, 91, 61, 14, 88, 9};
    for (int i = 0; i < sizeof(mass) / sizeof(int); i++)
        add_bin_tree(mass[i]);
    print(pHead, 0);
    //cout<< pHead->value<< " "<< pHead->left->value<< " "<< pHead->right->value<< " ";
    getch();
    return 0;
}
 
void add_node(bin_tree* tree, int value) // äîáГ*âëåГ*ГЁГҐ ГЄГ®Г*êðåòГ*îãî óçëГ* äåðåâГ*
{
    if(value < tree->value)
    { 
        if(tree->left != NULL) // åñëè Г§Г*Г*Г·ГҐГ*ГЁГҐ ìåГ*ГјГёГҐ, äâèãГ*åìñÿ ГЇГ® "ëåâîé ГўГҐГІГЄГҐ"
            add_node(tree->left, value);
        else
        {  
            tree->left = new bin_tree;
            tree->left->value = value;
            tree->left->left = NULL;
            tree->left->right = NULL;
        }
    }
 
    if(value > tree->value) // ГЁГ*Г*Г·ГҐ äâèãГ*åìñÿ ГЇГ® ГЇГ°Г*âîé 
    { 
        if(tree->right != NULL)
            add_node(tree->right, value);
        else
        {
            tree->right = new bin_tree;
            tree->right->value = value;
            tree->right->left=NULL;
            tree->right->right=NULL;
        }
    }
 
    if(value == tree->value)                
        cout<< value<< " is already in tree"<< endl;
}
 
void add_bin_tree(int value)
{
    if(pHead == NULL) // åñëè äåðåâî ïóñòîå - ñîçäГ*äèì ïåðâûé óçåë
    {
       pHead = new bin_tree;
       pHead->value = value;
       pHead->left = NULL;
       pHead->right = NULL;
    }
    else
        add_node(pHead, value); // åñëè Гў âåðøèГ*ГҐ óæå Г·ГІГ®-ГІГ® ГҐГ±ГІГј - äîáГ*âëÿåì ñëåâГ* èëè Г±ГЇГ°Г*ГўГ* 
}
 
void print(bin_tree* tree, int level)
{      
    if (tree->left != NULL) 
        print(tree->left, level + 1);
    for (int i = 0; i < level; i++)
         cout<< " ";
    cout<< tree->value<< endl;
    if (tree->right != NULL) 
       print(tree->right, level + 1);
}
2 вопроса:
1. Как можно сделать так, чтобы бинарное дерево создавалось с как можно меньшим количеством ярусов? Впринципе вот что пока на уме: отсортировать массив, взять за вершину дерева число, стоящее под индексом, равным размерности массива/2 либо (размерности массива/2 + 0,5). Но как тогда поступать, если нужно добавить новый элемент? Использовать вектор, или вобще все это изврат?
2. Хотелось бы создать функцию печати, чтобы видно было саму структуру дерева, но никаких идей на уме.

В интернете ничего дельного не нашел.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.10.2011, 00:53     бинарные деревья
Посмотрите здесь:

бинарные деревья - C++
Вершина двоичного дерева содержит указатель на строку и указатели на правое и левое поддеревья. Строки в дереве упорядочены по возрастанию....

Бинарные деревья - C++
Очень нужна помощь, вообще деревья не понимаю!!!:( Вершина дерева содержит указатель на строку и N указателей на потомков. Функция...

Бинарные деревья - C++
Подсчитать количество элементов на n-уровне бинарного дерева. Подскажите как можно решить используя любой обход в глубину но без...

Бинарные деревья - C++
Компилятор выдаёт ошибки в 9, 10 и 12, 13 строках: invalid conversion from 'int' to 'sNode*' Подскажите пожалуйста, что не так. ...

Бинарные деревья - C++
Разработать набор классов упорядоченных бинарных деревьев поиска типов: вещественные числа, двоичные строки(строка из 0 и 1) и линейные...

Бинарные деревья - C++
Возникла проблема с бинарными деревьями . Нужно определить K - количество узлов, ключ которых больше заданного числа N. Я дошёл только до...

Бинарные деревья - C++
Вот задачка: Для заданного бинарного дерева поиска проверить условие: • для каждой вершины высота левого поддерева отличается от...

Бинарные деревья - C++
Имею три файла: Скажите пожалуйста почему я не могу создать э-т m?(Класс tree) Он мне пишет - undefined reference to...

Бинарные деревья - C++
Здравствуйте! Подскажите, правильно ли написано правое удаление вершины дерева? if(tree1-&gt;Right){ if(tree1-&gt;Right-&gt;Left==NULL){ ...

Бинарные деревья - C++
На с++ с объектно-ориентированным подходом(тоисть с помощю класов) нужно представить арифметическое выражение типа 3*((7+1)/4)+(17-5) в...

Бинарные деревья - C++
Здравствуйте господа. Очень нуждаюсь в вашей помощи по бинарным деревьям. Собственно, имеется задание: Создать бинарное дерево которое...

бинарные деревья - C++
Здравствуйте! Помогите пожалуйста доделать задачу на бинарные деревья. Язык только начали изучать. Дается не очень легко. Пока...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CheToZudit
9 / 9 / 2
Регистрация: 22.10.2011
Сообщений: 19
22.10.2011, 05:42     бинарные деревья #2
У Вирта довольно подробно описано построение сбалансированного дерева. Там же по-моему можно найти форматированный вывод дерева. Найти такую книжку в интернетах не проблема

Добавлено через 54 минуты
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# include <iostream>
 
using namespace std;
 
class Tree          // tree
{
public:
    struct Node     // struct of Tree's elem
    {
        int key;
        Node *left;     
        Node *right;
        void PrintEl(int lvl);
    };
 
private:
    Node *root;     // ук-ль на корень дерева
    void Insert(int k, Node *&root);    // поиск и вставка эл-та
public:
    Tree() {root = 0;}
    Node* GetRoot() {return *&root ;}
    void BuildTree();   // build tree (:
    void TraceLeft(Node *root);
    void PrintTree();
};
 
int main()
{
    Tree tree;
    tree.BuildTree();
    cout << "It's your tree (:" << endl;
    //tree.TraceLeft(tree.GetRoot());
    tree.PrintTree();
    return 0;
}
 
void Tree::BuildTree()
{
    int k;      // it's temporary for key
    cout << "Enter key" << endl;
    while (cin >> k)
        Insert(k, root);
}
 
void Tree::Insert(int k, Node *&root)
{
    if (root == 0)
    {
        root = new Node;
        root->key = k;
        root->left = 0; root->right = 0;
    }
    else if (k < root->key)
            Insert(k, root->left);
        else if (k > root->key)
            Insert(k, root->right);
}
void Tree::TraceLeft(Node *root)
{
    if (root != 0)
    {
        TraceLeft(root->left);
        cout << root->key << " ";
        TraceLeft(root->right);
    }
}
void Tree::PrintTree()
{
    cout << endl;
    if (root)
        root->PrintEl(0);
}
void Tree::Node::PrintEl(int lvl)
{
    for (int i  = 0; i < lvl; i++)
        cout << " ";
    cout << key << endl;
    if (left)
        left->PrintEl(lvl + 1);
    if (right)
        right->PrintEl(lvl + 1);
}
Вот я кое-что наваял. Только весь код лучше не оценивать, мне за него немножко стыдно, а нужные функции форматированного вывода вроде нормально работают
MrGluck
Модератор
Эксперт CЭксперт С++
7158 / 4324 / 630
Регистрация: 29.11.2010
Сообщений: 11,745
26.10.2011, 12:08  [ТС]     бинарные деревья #3
Столкнулся с новой проблемой. Необходимо обойти бинарное дерево и сохранить последовательность прохождения вершин в файл. У меня записывает только корень дерева.

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <iostream>
#include <clocale>
#include <conio.h>
#include <fstream>
using namespace std;
 
struct node
{
    int Key; 
    int Count; 
    int bal; 
    node *Left, *Right;
};
 
class TREE 
{
  private:
    // h - ГґГ«Г*ГЈ, Г±ГЁГЈГ*Г*ëèçèðóþùèé îá óâåëè÷åГ*ГЁГЁ âûñîòû ïîääåðåâГ*:
    // true - âûñîòГ* ïîääåðåâГ* óâåëè÷èëГ*Г±Гј, 
    // false - âûñîòГ* ïîääåðåâГ* Г*ГҐ óâåëè÷èëГ*Г±Гј.
    bool h;
    node *Tree;
  public:
    TREE() {Tree = NULL; h = false;}
    void Search (int, node **);
    void Print (node **, int);
    void Traversal (node **);
    node** GetTree() {return &Tree;}
};
 
int main ()
{
    setlocale(LC_ALL, "Russian");
    TREE A;
    int el, n;
    cout<< "Êîëè÷åñòâî âåðøèГ* Гў äåðåâå: "; 
    cin>> n;
    cout<< "Г€Г*ôîðìГ*öèîГ*Г*ûå ïîëÿ âåðøèГ* äåðåâГ*:\n";
    for (int i=0; i < n; i++)
    { 
        cin>> el;
        A.Search (el, A.GetTree());
    }
    cout<< "\nÀÂË-äåðåâî:\n\n"; 
    A.Print (A.GetTree(), 0);
    A.Traversal (A.GetTree());
    getch();
    return 0;
}
 
void TREE::Search (int x, node **p)
// x - êëþ÷ âåðøèГ*Г», ïîìåùГ*åìîé Гў ÀÂË-äåðåâî.
// *p - ГіГЄГ*Г§Г*òåëü Г*Г* êîðåГ*Гј ÀÂË-äåðåâГ*.
// h - ГґГ«Г*ГЈ, Г±ГЁГЈГ*Г*ëèçèðóþùèé îá óâåëè÷åГ*ГЁГЁ âûñîòû ïîääåðåâГ*:
// true - âûñîòГ* ïîääåðåâГ* óâåëè÷èëГ*Г±Гј, 
// false - âûñîòГ* ïîääåðåâГ* Г*ГҐ óâåëè÷èëГ*Г±Гј.
// Ïðè ïåðâîì îáðГ*Г№ГҐГ*ГЁГЁ ГЄ ГґГіГ*êöèè Search() h=false.
{
    node *p1, *p2;
    h = false;
    if (*p == NULL) // åñëè ГіГЄГ*Г§Г*òåëü Г*Г* äåðåâî Г°Г*ГўГҐГ* 0
    {  
        *p = new(node);
        h = true; 
        (**p).Key = x; 
        (**p).Count = 1; 
        (**p).Left = (**p).Right = NULL;
        (**p).bal = 0; 
    }
    else 
    if (x <= (**p).Key) 
    {
        Search (x, &((**p).Left)); 
        if (h == true)
            switch ((**p).bal) 
            { 
                case 1 :  (**p).bal = 0; h = false; break; 
                case 0 : (**p).bal = -1; break; 
                case -1: 
                          p1 = (**p).Left; 
                          if ((*p1).bal==-1) 
                          {    
                              (**p).Left = (*p1).Right; 
                              (*p1).Right = *p; 
                              (**p).bal = 0; 
                              *p = p1; 
                          } 
                          else 
                          {
                              p2 = (*p1).Right; 
                              (*p1).Right = (*p2).Left; 
                              (*p2).Left = p1; 
                              (**p).Left = (*p2).Right; 
                              (*p2).Right = *p;
                              if ((*p2).bal == -1) 
                                  (**p).bal = 1; 
                              else 
                                  (**p).bal = 0; 
                              if ((*p2).bal == 1) 
                                  (*p1).bal = -1; 
                              else 
                                  (*p1).bal = 0;
                              *p = p2;
                          } 
                          (**p).bal = 0; 
                          h = false; 
                          break; 
            }
    }
    if (x > (**p).Key) 
    {    
        Search (x, &((**p).Right)); 
        if (h == true)
            switch ((**p).bal) 
            { 
                case -1: (**p).bal = 0; h = false; break; 
                case  0: (**p).bal = 1; break;
                case  1:
                          p1 = (**p).Right; 
                          if ((*p1).bal == 1) 
                          {
                              (**p).Right = (*p1).Left; 
                              (*p1).Left = *p; 
                              (**p).bal = 0; 
                              *p = p1; 
                          } 
                          else
                          {
                               p2 = (*p1).Left; 
                               (*p1).Left = (*p2).Right; 
                               (*p2).Right = p1; 
                               (**p).Right = (*p2).Left; 
                               (*p2).Left = *p; 
                               if ((*p2).bal == 1) 
                                   (**p).bal = -1; 
                               else 
                                   (**p).bal = 0; 
                               if ((*p2).bal == -1) 
                                   (*p1).bal = 1; 
                               else 
                                   (*p1).bal = 0; 
                               *p = p2; 
                          } 
                          (**p).bal = 0; 
                          h = false; 
                          break;
             }
    }
}
 
void TREE::Print (node **w, int lvl)
//ÈçîáðГ*æåГ*ГЁГҐ äåðåâГ* w Г*Г* ГЅГЄГ°Г*Г*ГҐ äèñïëåÿ
//         (ðåêóðñèâГ*ûé Г*ëãîðèòì).
//*w - ГіГЄГ*Г§Г*òåëü Г*Г* êîðåГ*Гј äåðåâГ*.
{
    if  (*w != NULL)
    {
        Print (&((**w).Right), lvl + 1);
        for (int i = 0; i < lvl; i++) 
            cout<< "   ";
        cout<< (**w).Key<< endl;
        Print (&((**w).Left), lvl + 1);
    }
}
 
void TREE::Traversal (node **w)
//*w - ГіГЄГ*Г§Г*òåëü Г*Г* êîðåГ*Гј äåðåâГ*.
{
    ofstream o("bin.txt");
    if  (*w != NULL)
    {
        Traversal (&((**w).Right));
        o<< (**w).Key<< " ";
        Traversal (&((**w).Left));              
    }
    o.close();
}
Добавлено через 16 часов 49 минут
Цитата Сообщение от MrGluck Посмотреть сообщение
Необходимо обойти бинарное дерево и сохранить последовательность прохождения вершин в файл. У меня записывает только корень дерева.
ап...
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
26.10.2011, 12:40     бинарные деревья #4
Цитата Сообщение от MrGluck Посмотреть сообщение
бинарное дерево создавалось с как можно меньшим количеством ярусов?
Использовать алгоритмы балансировки деревьев: AVL, red-black.
Цитата Сообщение от MrGluck Посмотреть сообщение
Хотелось бы создать функцию печати, чтобы видно было саму структуру дерева, но никаких идей на уме.
Обычный обход делайте, этого будет достаточно.
MrGluck
Модератор
Эксперт CЭксперт С++
7158 / 4324 / 630
Регистрация: 29.11.2010
Сообщений: 11,745
26.10.2011, 13:00  [ТС]     бинарные деревья #5
Цитата Сообщение от fasked Посмотреть сообщение
Использовать алгоритмы балансировки деревьев: AVL, red-black.

Обычный обход делайте, этого будет достаточно.
Да, я решил использовать АВЛ деревья.

При обходе, если делать вывод на экран, то выводит все вершины, если сделать вывод в файл, выводит только одну, а конкретно корень дерева. (пост 3)
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
26.10.2011, 14:08     бинарные деревья #6
Цитата Сообщение от MrGluck Посмотреть сообщение
При обходе, если делать вывод на экран, то выводит все вершины, если сделать вывод в файл, выводит только одну, а конкретно корень дерева. (пост 3)
C++
1
2
3
4
5
6
7
8
9
10
11
12
void TREE::Traversal (node **w)
//*w - указатель на корень дерева.
{
    ofstream o("bin.txt");
    if  (*w != NULL)
    {
        Traversal (&((**w).Right));
        o<< (**w).Key<< " ";
        Traversal (&((**w).Left));
    }
    o.close();
}
В данном коде объект ofstream создается каждый раз. Следовательно, он переписывает файл при каждом вызове метода Traversal. В итоге в файле - значение первой вызванной (последней закрытой) функции. Вообще странно, что код отрабатывает. Потому что несколько объектов ofstream обращается к незакрытому файлу.
Yandex
Объявления
26.10.2011, 14:08     бинарные деревья
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru